SECTION 1

Exercise # 1)  For each of these pairs of integers, determine whether they are congruent modulo 7.

a) 1, 15

b) 0, 42

c) 2, 99

d) -1, 8

e) -9, 5

f )-1, 699

Exercise # 2)  Show that if a is an even integer, then a²≡ 0 (mod 4), and if a is an odd integer, then a²≡ 1 (mod 4).

Exercise # 3)  Find the least nonnegative residue modulo 13 of each of the following integers.

a) 22

b) 100

c) 1001

d) -1

e) -100

f) -1000

Exercise # 4)  Show that if a, b, m, and n are integers such that m>0, n >0, n | m, and a ≡ b (mod m), then a ≡ b (mod n).

Exercise #5)  Construct a table for multiplication modulo 6. (Using the least nonnegative residues modulo 6 to represent the congruence classes)

Exercise # 6)  Show that if n is an odd positive integer or if n is a positive integer divisible by 4, then 1² + 2² + 3³ + . . . + (n-1)³ ≡ 0 (mod n). Is this statement true if n is even but not divisible by 4?

Exercise # 7)  Show by mathematical induction that if n is a positive integer, then 4ⁿ ≡ 1+3n (mod 9). 

SECTION 2

Exercise # 1) Find all solutions of each of the following linear congruences.

a) 3x ≡ 2 (mod 7)

b) 6x ≡ 3 (mod 9)

c) 17x ≡ 14 (mod 21)

d) 15x ≡ 9 (mod 25)

e) 128x ≡ 833 (mod 1001)

f ) 987x ≡ 610 (mod 1597)

Exercise # 2)   Suppose that p is prime and that a andb are positive integers with (p, a) = 1. The following method can be used to solve the linear congruence ax ≡ b (mod p).

a) Show that if the integer x is a solution of ax ≡ b (mod p), then x is also a solution of the

linear congruence a₁x ≡ -b[m/a] (mod p), where a₁ is the least positive residue of p modulo a. Note that this congruence is of the same type as the original congruence, with a positive integer smaller than a as the coefficient of x.

b) When the procedure of part (a) is iterated, one obtains a sequence of linear congruences with coefficients of x equal to a_n=a >a₁>a₂> . . . . Show that there is a positive integer n with a_n= 1, so that at the nth stage, one obtains a linear congruence x ≡ B (mod p).

c) Use the method described in part (b) to solve the linear congruence 6x ≡ 7 (mod 23).

Exercise # 3)Find an inverse modulo 13 of each of the following integers.

a) 2

b) 3

c) 5

d) 11

Exercise # 4)

a) Determine which integers a, where 1≤ a ≤ 14, have an inverse modulo 14.

b) Find the inverse of each of the integers from part (a) that have an inverse modulo 14.

Exercise # 5)  Find all solutions of each of the following linear congruences in two variables.

a) 2x + 3y ≡ 1 (mod 7)

b) 2x + 4y ≡ 6 (mod 8)

c) 6x + 3y ≡ 0 (mod 9)

d) 10x + 5y ≡ 9 (mod 15)

SECTION 3

Exercise # 1)  Find an integer that leaves a remainder of 1 when divided by either 2 or 5, but that is divisible by 3.

Exercise # 4)  Find all the solutions of each of the following systems of linear congruences.

a)x≡ 4 (mod 11)

x≡ 3 (mod 17)

 b)x≡ 1 (mod 2)

x≡ 2 (mod 3)

x≡ 3 (mod 5)

 c)x≡ 0 (mod 2)

x≡ 0 (mod 3)

x≡ 1 (mod 5)

x≡ 6 (mod 7)

d)  x≡ 2 (mod 11)

x≡ 3 (mod 12)

x≡ 4 (mod 13)

x≡ 5 (mod 17)

x≡ 6 (mod 19)

Exercise # 2)  As an odometer check, a special counter measures the miles a car travels modulo 7. Explain how this counter can be used to determine whether the car has been driven 49,335; 149,335;or 249,335 miles when the odometer reads 49,335 and works modulo 100,000.

Exercise # 3)  Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.

Exercise # 4)  Show that the system of congruences

x≡ a₁(mod m₁)

x≡a₂(mod m₂) has a solution if and only if (m₁, m₂) | (a_1-a₂). Show that when there is a solution, it is unique modulo [m₁, m₂]. (Hint: Write the first congruence as x = a₁+ km₁, where k is an integer, and then insert this expression for x into the second congruence.)

Exercise # 5)  Using Exercise 15, solve each of the following simultaneous systems of congruences.

a)x≡ 4 (mod 6)

x≡ 13 (mod 15)

b)x≡ 7 (mod 10)

x≡ 4 (mod 15)

SECTION 4

Exercise # 1)  Find all the solutions of each of the following congruences.

a) x³+ 8x²-x -1≡0 (mod 11)

b) x³+ 8x²-x -1≡0 (mod 121)

c) x³ + 8x²-x -1≡0 (mod 1331)

Exercise # 2)  Find all solutions of x⁸- x⁴+ 1001≡ 0 (mod 539).

Exercise # 3) How many incongruent solutions are there to the congruence x⁵ + x - 6 ≡ 0 (mod 144)?

EXERCISE #4)Compute the least positive residue modulo 10,403 of 7651⁸⁹¹

EXERCISE #5)Compute the least positive residue modulo 10,403 of 7651^20!