Section 3: Exercises

Math 250: Exercises for Section 3

This page contains only exercises. See the Course Calendar link for specific exercise collection dates.

You will find some special notation on this page:

a =_n b denotes that a is congruent to b modulo n.

Sqrt(n) denotes the square root of n.

phi(n) denotes the number of positive integers that are less than n and relatively prime to n.

Sum _indices [terms] denotes the sum of the specified terms over the designated indices.

Instructions for submissions.

Put each proof on a separate sheet of paper.

Clearly write out the statement that you are proving.

Clearly note where the proof begins[by writing either "Proof" or "Prf" in the margin] and ends.

Exercises for

Exercises for Section 3.1
Exercises for Section 3.2
Exercises for Section 3.3
Exercises for Section 3.4
Exercises for Section 3.5
Exercises for Section 3.6
Exercises for Section 3.7
Exercises for Section 3.8

Section 3.1

1. Complete the proof of Theorem 3.2

2. Let a, b, and c be arbitrary integers. Then

i. a =_n b implies b =_n a, and
ii. a =_n b and b =_n c implies a =_n c.
iii. a =_n b and d =_n e implies a + d =_n b + e.

3. Reduce 437 ⁷⁹ mod 6

4. For any odd natural n, 1 + 2 + 3 + ... + (n - 1) =_n 0. [See the proof submitted by Group 1]

5. If p > 3 is prime, then 1² + 2² + 3² + ... + (p - 1)² =_p 0. Show that this statement is false if p is not prime.

Hint: To prove the statement when p is prime, you may first want to prove that 1² + 2² + 3² + ... + (n)² = (1/6)(n)(n + 1)(2n + 1) for all natural n. BUT, be very careful how you use this idea.

6. Let a =_n b. Then a^m =_n b^m for all m > 1.

7. Complete the proof of Theorem 3.5

8. Prove Theorem 3.7.

Section 3.2

1. Complete Theorem 3.9 by proving: If the linear congruence aX =_n b has a solution, then (a,n) divides b. [See the proof submitted by Group 3]

2. Find all incongruent solutions to 2X + 6Y =₁₀ 8.

3. If (a,n) = 1 or (b,n) = 1, then the linear congruence aX + bY =_n c has exactly n incongruent solutions.

4. Find all incongruent solutions to the linear congruence 3X + 5Y =₆ 10.

Section 3.3

1. Find the smallest positive integer that gives remainders 5, 4, 3, and 2 [respectively] when divided by 6, 5, 4, and 3 [respectively] [Bhramagupta, 7th century AD]

Hint: The CRT does not apply to the system of congruences that is associated to this problem. But, if you're clever you can reduce the system to a new system involving two modular congruences that might be solvable.

[See the result regarding systems of two linear congruences submitted by Groups 2 and 4]

Section 3.4

1. Complete the proof of the lemma to Theorem 3.14.

2. Prove Theorem 3.15

3. For every prime p, (p - 1)! =_s (p - 1) where s = 1 + 2 + 3 + ... + (p - 1).

4. If p = 4n + 1 is prime, then [(2n)!]² =_p -1. [NB. In arithmetic modulo p, there is a 'number' that behaves like the imaginary number i.] [See the proof submitted by Group 4]

Hint: A direct proof using Wilson's Theorem will get the job done. But you will need to be sure to include the following:
For 1 < j < 2n, show that (2n + j) =_p (-2n + (j - 1)).

5. If p is an odd prime and n is a positive integer < p, then (p - n)!(n - 1)! =_p (-1)ⁿ. [See the proof submitted by Group 2]

Hint: For p and n as above, note (p - 1)! = (p - 1)*(p - 2)* ... *(p - (n - 1))*(p - n)!

Section 3.5

1. Show 2³⁴¹ = 2 (mod 341). What does this tell you about using Fermat's Little Theorem to characterize prime numbers?

2. Prove Theorem 3.17

3. If p is prime, then 1^{(p - 1)} + 2^{(p - 1)} + ... + (p - 1)^{(p - 1)} + 1 = 0 (mod p). [See the proof submitted by Group 1]

4. Let p be prime and a and b be integers with (a,p)=1 and (b,p) =1. If a^p = b^p (mod p), then a = b (mod p).

Section 3.6

1. If n > 2, then phi(n) is even.

2. If m | n, then phi(mn) = m*phi(n).

Hint: A direct proof is easiest, but you have to decide which version of Theorem 3.21 you're going to use.

3. Prove phi( n² ) = n*phi(n).

4. Prove Theorem 3.22.

5. Prove Sqrt(n) / 2 < phi(n).

6. If n has r distinct prime factors, then 2 ^r-1 | phi(n). Note the original statement, 2^r | phi(n), is false. [See the proof submitted by Group 3]

7. If n > 1 and n has r distinct prime factors, then phi(n) > n / (2^r ).

8. Show that the phi function is not onto.

Section 3.7

1. Reduce 72⁹³² (mod 35).

2. If p be an odd prime, then { -(p-1)/2, ... , -2, -1, 1, 2, ... , (p-1)/2 } is a reduced residue system modulo p. [See the proof submitted by Group 1]

3. Fix n to be natural. If a is an integer with (a,n) = (a-1,n) = 1, then 1 + a + a² + ... + a^{(phi(n) - 1)} =_n 0. [See the proof submitted by Group 4]

Hint: Recall a^phi(n)- 1 = (a - 1)*( a^{(phi(n)
- 1)} + ... + a² + a + 1).

4. Let m and n be naturals. If (m,n) = 1, then m^phi(n) + n^phi(m) =_mn 1.

Section 3.8

1. Fix a, b, and c integers with a odd. Determine the conditions under which the quadratic congruence aX² + bX + c =₂ 0 has a solution. Prove your conjecture. [See the solution submitted by Group 3]

2. Complete the proof of Theorem 3.28 by proving the following: Let d be a quadratic residue modulo p. Let S be the set of naturals {1, 2, ... , p-1} with y and p-y removed where y² =_p d and 1 < y < p-1. For any c in S, there is a number c' in S with cc' =_p d and c not equal to c'. [See the proof submitted by Group 2]

3. Does 4X² + 2X - 1 =₂₁ 0 have solutions?

4. Does 3X² + 13X - 7 =₃₂₃ 0 have solutions?