Due July 18 (Friday), whether late submission is accepted or not is up to Sujatha.

The exercises all come from the textbook (6th edition). In case you don’t have the book, I copied the questions and posted them here.

These exercises are either simple proofs or direct computations. Don’t be afraid. If you keep good notes in class, you can finish them fairly quickly.

3.1 Exercise (p.76) #12, #18

#12. Show that if is the th prime, then .

Proof. Take any prime divisor of . Then

Since none of divides , we see that is distinct from . In particular,

Combining (1) and (2), we are done.

#18. Use Dirichlet’s theorem to show that there are infinitely many primes whose decimal expansion ends with the two digits 23.

Proof. By Dirichlet’s theorem, there are infinitely many primes in the sequence . Clearly, each such prime ends with digits 23 in its decimal expansion.

3.3 Exercise (p.100) #24

#24. Show that if is a positive integer, then and are relatively prime. (Hint: use the “spirit” of the Euclidean algorithm: .)

Proof. Indeed, we have

.

In each step, I only subtract one copy of the smaller number from the larger one. (Of course, the statement remains true for all integers *k*.)

3.4 Exercise (p.110) #1 a), b), c), #3

#1. Use the Euclidean algorithm to find each of the following greatest common divisors (gcd).

a) (45, 75)

b) (102, 222)

c) (666, 1414)

Answer. I want to skip the detailed computation. The answers are a) 15; b) 6; c) 2.

#3 For each pair in Exercise #1, express the gcd of the integers as a linear combination of these integers. (That is, you need to write as for some integers .) Only do a), b), c) above.

Answer. Detailed computation omitted. (The following are sample answers coming from the Euclidean algorithm. Other answers exist.)

a) .

b) .

c) .

3.5 Exercise (p.123) #44

#44. Show that is irrational. (Hint: Use fundamental theorem of arithmetic (optional) and proof by contradiction.)

Proof. Assume the contrary. Then we can write where are integers. Then we have , or . The LHS is even while the RHS is odd. Contradiction.

3.7 Exercise (p.141) #2 a), b), c)

#2. For each of the following linear Diophantine equations, either find all solutions or show that there are no solutions.

a)

b)

c)

Answer. Detailed computations omitted.

a) All integer solutions: , , .

b) No integer solutions, because 6 divides the LHS, but not the RHS.

c) All integer solutions: , , .

4.1 Exercise (p.153) #30, #33

#30. Show by mathematical induction that if is a positive integer, then .

Proof. The case for is trivial. Now suppose that the congruence holds for . Then

,

showing that the formula holds for . By induction, the formula holds for all .

#33. Show that if , then cannot be the sum of the squares of two integers. (Hint: You may find the last problem in Homework 1 useful.)

Proof. If is an odd integer, then from homework 1, we know . If *m* is even, then plainly . Therefore, the sum of two squares is congruent to 0, 1, or 2 mod 4. But , thus it cannot be the sum of two integers.

FYI, the set of integers is explicitly known. In particular, it contains all primes which are congruence to 1 mod 4.

4.3 Exercise (p.167) #4 c)

#4. Find all the solutions of the following system of linear congruences.

c)

Answer. Actually you don’t need to compute it using Euclidean algorithm. There is one obvious solution: 6. Therefore by the Chinese remainder theorem, all solutions are: , .