Marywood University Department of Mathematics Course Information for Math 323 Number Theory by Dr. J.

Carl Friedrich Gauss (1777-1855)

An introduction to Number Theory. This course is required for both mathematics and math/secondary education majors. Topics include divisibility properties, congruences, residue systems, quadratic reciprocity, cryptography, and number-theoretic functions. . The textbook is Introduction to Number Theory by Calvin Long and published by Harcourt and Academic Press. The course grade is determined by three tests, 10 homework sets, and a final examination. Useful websites are listed at the end of this page. Prerequisite: Math 202 (Calculus II). Comments to Dr. Craig M. Johnson, Chair, Dept. of Mathematics: johnsonc@marywood.edu

Sample Problems for Test #1

• Prove: S [1/i(i+1)] = n/(n+1) for all n in N.
• Prove: If F_i = ith Fibonacci number, then S (F_i)² = F_nF_n+1 for all n in N.
• Express 275₁₀ in base 7, base 2, and base 16.
• Use the well-ordering principle to prove that sqrt(7) is irrational.
• Prove that one of any three consecutive integers is divisible by 3.
• Prove that one of any six consecutive integers is divisible by 6.
• If the following statement is true, then prove it. If it is false, provide a counter-example: If a² | b³, then a | b.
•  
• Determine (210, 495) and [210, 495]. Express (210, 495) as a linear combination 210x + 495y with x, y in Z.
• Find (312, 240, 108) and [312, 240, 108].
• If (a, b) = 1, prove that (a+b, a-b) = 1 or 2.
• Evaluate t(5112) and s(5112).
• If b | c , prove that (a, b) = (a + c, b).
• Prove: t(n) is odd iff n is a perfect square.
• Find an integer n such that s(n) = 91.
• Prove: There are infinitely many primes.

Sample Problems for Test #2

• Show that the set { 18, -5, -10, 27, 4, 11 } forms a complete residue system modulo 6.
• Find the least residue of:
  • 18316 modulo 17
  • (113 • 55137 + 457250 • 27) modulo 9
• The nth triangular number is given by t(n) = n(n+1)/2 . Show that every even perfect number is triangular.
• If a is congruent to b (mod m) and c is congruent to d (mod m), then prove that a + c is congruent to b + d (mod m).
• How many of the elements of the group (Z₆₃,+) are generators of the group?
• Compute the value of f(7200). If a is relatively prime to 7200, then show that a³⁸⁴⁰ is congruent to 1 (mod 7200)
•  
• Find the solutions to each of the following linear congruences. (Consider these separately. This is not a system.)
  • 6x is congruent to 5 (mod 14)
  • 8x is congruent to 12 (mod 20)
• Find the least positive integer that leaves remainders of 1, 3, and 6 when divided by 2, 5, and 9 respectively.
• Find the quadratic character of 41 with respect to 59.
• Determine the quadratic residues mod 13.
• If possible, solve the congruence equation: 7x² - 4x + 1 is congruent to 0 (mod 11).

Sample Problems for Test #3

• Decipher this message if an exponentiation cipher was used with modulus p = 127 and key k = 23.

  102 86 86 83

• Let E_X represent the enciphering function of person X (which is known by everyone) in a public key encryption system and let D_X represent the deciphering function of person X. If person A sends a signed message M to person B, how can person B be sure the message came from A ?
• The famous spy Maxwell Smart risked his life to discover that the most frequently used two letters in the plaintext messages by the evil organization Chaos are A and S, respectively. While taking a break from studying for her number theory final, Agent 99 intercepted the following enciphered message from Chaos:

  H F S K F J M F T H

  Decipher the message assuming that it was encrypted with a generalized Caesar cipher.

• If f is multiplicative, m | n, and (m, n/m) = 1, show that f(n/m) = f(n)/f(m).
• Let r = number of distinct primes in the canonical representation of n. Prove that S | m(d) | = 2^r where the sum is over the divisors d of n.
• Let r = number of distinct primes in the canonical representation of n. Let f(n) = S m(d) t(d) where the sum is over the divisors d of n. prove that f(n) = (-1)^r.
• If g(n) = S m(d) s(d) where the sum is over the divisors d of n, find a formula for g(n) in terms of the canonical representation of n.
• If h(n) = S m(d) f(d) where the sum is over the divisors d of n, find a formula for h(n) in terms of the canonical representation of n.
• If n is perfect, show that S (1/d) = 2 , where the sum is over the divisors d of n.
• Let f(n) = S f(d) where the sum is over the divisors d of n.
  • Show that f(p^m) = p^m if p is prime.
  • Assuming f is multiplicative, show that f(n) = n.

Useful Websites

http://www.mapleapps.com/index.asp (The Maple Applications Center)

http://www.maa.org (Mathematical Association of America)

http://archives.math.utk.edu (Math Archives)

http://forum.swarthmore.edu (Math Forum)

Marywood University <|> Undergraduate School <|> Undergraduate Admissions

Last update: October 31, 2003 by Craig Johnson

Copyright © 2003 by Marywood University. All rights reserved. Marywood University, 2300 Adams Avenue, Scranton, PA 18509 (717) 348-6211