Problem 1.   [8 points] Prove the following statements.

a)  Let n e Z. If 8 ∤ (n2 − 1) then 2 ∣ n.

b)  Let a,b,c e Z. If a ∣ c, b ∣ c, and gcd(a,b) = 1, then ab ∣ c.

Problem 2.   [7 Points] Consider the line segment connecting (0, 0) and (a,b) e Z × Z ⊆ R2 . Write down the equation of this line segment.

a)  Conjecture number of points with integer coordinate that this line segment intersects using the following examples.

• the line from (0, 0) to (3, 1) intersects 2 points with integer coordinates, (0, 0) and(3, 1).

• the line from (0, 0) to (4, 2) intersects 3 points with integer coordinates, (0, 0), (2, 1), and (4, 2).

• the line from (0, 0) to (12, 28) intersects 5 points with integer coordinates, (0, 0), (3, 7), (6, 14), (9, 21) and (12, 28).

• the line from (0, 0) to (30, 66) intersects 7 points with integer coordinates, (0, 0), (5, 11), (10, 22), (15, 33), (20, 44), (25, 55) and (30, 66).

• the line from (0, 0) to (390, 210) intersects 31 points with integer coordinates, (0, 0), (13, 7), (26, 14), (39, 21), (52, 28), (65, 35), … , (390, 210).

b)  Prove your conjecture.

Problem 3.   [15 points]

a)  Prove that all odd primes are in the form 4q + 1 or 4q + 3? Example: 29 = 4 ⋅ 7 + 1 or 43 = 4 ⋅ 10 + 3

b)  Prove that at least one of the prime divisors of a natural number in the form 4q + 3 is of the form 4q + 3.

Example:  15 = 4 ⋅ 3 + 3 = 5 ⋅ 3 = 5(4 ⋅ 0 + 3) or 143 = 4 ⋅ 35 + 3 = 11 ⋅ 13 = (4 ⋅ 2 + 3) ⋅ 13   Hint 1: It is proven that “Every natural number except 1 has at least one prime divisor.”

Hint 2: The result of part a can be used in this part.

c)  Suppose x e Z and y  Z. Prove that x + y  Z

d)  Modify the given proof in Test Yourself Exercise 5.22 and use the results of parts a-c and show that there are infinitely many prime numbers of the form 4q + 3.

Hint  1:  In your proof, consider the number Q = 4 ⋅ p1  ⋅ … ⋅ pn  − 1 where p1 ,p2 , . . . ,pn  are in the form 4q + 3.

Problem 4.   [10 points] Use B´ezout’s Identity (the following theorem) and prove the statements in parts a-c.  Note that proofs that do not use B´ezout’s Identity somewhere in the proof process, will get no point.

Theorem 1.  (B´ezout’s Identity) Let a,b e Z .  Then gcd(a,b) is the smallest element in the set of integer linear combinations of a and b {ax + by∣x,y e Z,ax + by > 0}.

a)   Using B´ezout’s Identity prove that there is no integers x and y  that satisfy the equation 4x + 12y = 1.

b)   Using B´ezout’s Identity prove that if a,b,c are positive integers such that gcd(a,b) = 1 and a ∣ bc, then a ∣ c.

c)  Let p be a prime number.  Using B´ezout’s Identity prove that for every a,b e Z, if p ∤ a and p ∤ b then p ∤ ab.

Problem 5.   [10 points] A very famous unsolved problem in Number Theory is the Collatz con-

jecture.

Let a0  be a positive integer. Then we generate a sequence of integers a0 ,a1 ,a2 , . . . as follows:

ai+1  = {

The Collatz conjecture asserts that for any positive integer a0 , this sequence will always eventually reach 1.

For example, let a0  = 3, then we generate the sequence as follows:

As a0  = 3 is odd, then a1  = 3(a0 ) + 1 = 3(3) + 1 = 10.

As a1  = 10 is even then a2  = a1 \2 = 10\2 = 5

As a2  = 5 is odd then a3  = 3(5) + 1 = 16

As a3  = 16 is even then a4  = 16\2 = 8

As a4  = 8 is even then a5  = 8\2 = 4

As a5  = 4 is even then a6  = 4\2 = 2

As a6  = 2 is even then a7  = 2\2 = 1.

Thus we see after 7 iterations the sequence reaches 1.

a)  Implement a function with signature

def  collatz_function(a):

which when given a positive number ai  returns ai+1  according to the definition of the Collatz sequence, e.g. on input 3 your function should return 10.

b)  Implement a function with signature

def  collatz_sequence(a):