Suppose that p is prime and that a and b are positive integers with (p, a)= 1. The following method can be used to solve the linear congruence a x equiv b (mod p). a) Show that if the integer x is a solution of a x equiv b (mod p), then x is also a solution of the linear congruence a_1 x equiv-b[m / a]( bmod p) where a_1 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_0=a>a_1>a_2> cdots. Show that there is a positive integer n with an= 1, so that at the nth stage, one obtains a linear congruence x equiv B (mod p). c) Use the method described in part (b) to solve the linear congruence 6 x equiv 7 (mod 23).
