Math 58 – Elementary Number Theory

October 5, 2006

What’s on the Exam? #1

First-page header (subject to revision)

Name_____________________________

Math 58 – Elementary Number Theory

October 5, 2006

Exam 1 – Due at start of class Tuesday, October 10

Take this exam at a time and place of your choosing. There is no time limit, but you are enjoined from discussing math with anyone except the instructor between starting and ending the exam, so you should plan on completing it in a single session. You may use a calculator but not a computer or any references. You may use this paper, your own paper, or both. It isn’t necessary to turn in scratch paper. There are 15 numbered questions on 3 pages.

Show your work. (It may sometimes be necessary for full credit, and it’s always necessary for part credit.)

Return this exam in class or to my office by 11:20am on Tuesday, October 10.

(1) Be able to do these computations…

compute the gcd of two or more numbers, of up to, say, 10 digits.

compute the lcm of two or more numbers, provided their product is at most,

say, 10 digits. (One method: [ x, y, z ] = xyz – ( x, y, z ). )

compute the gcd and lcm of two or more numbers much more quickly if

given their prime factorizations.

given a, b, n, decide whether n can be written as n = xa + yb for

for (positive or negative) integers x and y, and if possible, find

x and y

evaluate binomial coefficients,

convert an integer from decimal representation to binary, or vice versa

find the least non-negative residue of a (mod m)

given a and m, decide whether a has a multiplicative inverse (mod m), and

and if so, find a^-1 (mod m)

find all x that satisfy ax = c (mod m), even if (a,m) is not 1

calculate products and exponents (mod m) without fear, e.g. a^b or a! (mod m),

even when a, b are fairly large (also know some shortcuts for

these; see below)

Chinese remainder theorem: If m₁, …, m_r are pairwise relatively prime

and a₁, …, a_r are given, find x such that x = a_i (mod m_i) for

each i, and know that x is unique mod m₁m₂…m_r. (The case in

which the m’s are not pairwise relatively prime is not on the exam.)

Find the prime factorization of n, if n is small enough that trial division

works

Find the prime factorization of n, if n is given in a form that permits

trickery, such as the difference of two squares

Given a prime p and a primitive root g for the integers mod p, list all of

the k-th powers (mod p). (They are 1, g^k, g^2k, g^3k, etc…; the

exponents might stop at g^p-1 or keep going for more cycles

according to whether k is a factor of p-1.)

(2) Notations

(a, b) = gcd of a, b

(a, b, c, …) = gcd of a, b, c, … = ( a, (b, c, … ) )

[a, b] = lcm of a, b

[a, b, c, …] = lcm of a, b, c, …

[a] = congruence class of a, if modulus is understood

all numbers are integers unless clearly stated otherwise, but we make

no automatic assumption about whether they are positive

primes are always positive

Z_m = system of integers mod m. (Perhaps not a system of integers at all, but

a system of congruence classes mod m with + and ´ defined for

congruence classes)

Z_p* = system of non-zero integers mod p, if p is prime (Analogous

notation for non-primes not introduced yet)

(3) Some random theorems

Any common divisor of a, b, c,… is a divisor of (a, b, c, …)

Any common multiple of a, b, c… is a multiple of [a, b, c… ]

Division algorithm: Given integers a and b with b positive, there are unique

integers q, r such that a = qb + r and 0 ≤ r < b.

a has a multiplicative inverse mod m if, and only if, (a,m)=1.

(Wilson) (p-1)! = -1 (mod p) if, and only if, p is prime.

(Fermat’s Little Theorem) a^p = a (mod p) if p is prime, for any a.

Equivalently: If p is prime and p does not divide a, then a^p-1 = 1 (mod p).

Primitive roots: If p is a prime, there is an integer g in Z_p such that all non-zero

elements of Z_p are powers of g. (We have declared this to be true,

but we haven’t proven it yet.)

There are infinitely many primes

There are arbitrarily long sequences of evenly spaced primes (not proven

in class)

There are arbitrarily long sequences of positive composite numbers

The density of primes in the neighborhood of x is about 1/ln(x) (heuristic)

The number of primes less than x, called p(x), is about x/ln(x),

or more accurately Li(x) = . (True in limit; that is,

lim p(x)/Li(x) = 1, but not proved in class)

(4) Bloopers, rejects, and practice problems

1. State the “division algorithm.”

2. State precisely the fundamental theorem of arithmetic.

3. Evaluate: ( 8174, 12261) and [ 125, 15 ]

4. Express in base-10 notation: (1111000)₂

5. Find the prime factorization of 6237.

6. What is the prime factorization of 4087 ? (Hint: 64² = 4096)

7. Express 7 as a linear combination of 15 and 4, or prove that it is impossible.

8. Express 7 as a linear combination of 15 and 50, or prove that it is impossible.

9. The 5th prime is 11. Prove by induction that if n ≥ 5, then the n-th prime is

larger than 2n.

10. Can there be 19 consecutive composite integers, all greater than 1 ?

(Prove your answer)

11. Find all integers x such that 10x = 9 (mod 64) or prove that no such

x exists.

12. Write a complete residue system (mod 8).

13. Find an integer x such that all of these congruences are true:

x=1 (mod 2) x=2 (mod 3) x=4 (mod 7)

14. Now find another integer x satisfying the conditions of problem 13.

15. What is 2³² (mod 30) ?

16. What is 92¹⁹⁰⁸⁰ (mod 19081) ? How about 92¹⁹⁰⁹² ?

(end)