# Congruences : Primes, Inverse Modulo, GCD and Wilson's theorem

Please assist me with the attached congruence problems (hint: use Wilson's Theorem)

a)Prove if a,b,c Z, N and gcd (c, ) = , then ac bc(mod ) if and only if

a b (mod ).

b) Let a Z, N, and p > 2 be a prime. Prove that a is its own inverse modulo p if and only if a 1 (mod p ).

C) Let a,b Z, N .prove that ax b(mod ) has a solution if and only if gcd (a, ) b.

d) Suppose that 3(mod 4) is prime. Prove that

)! 1 (mod )

Hint( Use Wilson's Theorem)

Please see the attached file for the fully formatted problems.

#### Solution Preview

a)Prove if a,b,c elements of Z, n element of N and gcd (c, n) = g, then ac is congruent to bc(mod n ) if and only if

a is congruent to b (mod n/g ).

_____________________________________________

(i) if: suppose a is congruent to b (mod n/g). (note that g must divide n because g = gcd (c,n) so that n/g is an integer)

Then a = b + kn/g for some integer k (definition of congruence)

So ac = bc + kcn/g (multiplication, integers so we can commute and associate)

Since g = gcd (c,n), g divides both c and n; c/g is an integer; let c/n = j

Then ac = bc + kjn where kj is an integer, and thus ac is congruent to bc modulo n by definiton

(ii) only if: Suppose ac is congruent to bc modulo n

Then ac = bc + hn for some integer h, by definition of congruence

Since g = gcd (c,n), c = gd and n = gf for some integers f and d, and gcd (d,f) = 1

(by definition of gcd); note f = n/g as needed

Substituting, agd = bgd + hgf

Dividing out the g (g is an integer not equal to zero, because a gcd is always 1 or greater)

ad = bd + hf

Dividing out the d,

a = b + (hf)/d

Since a and b are integers, which are closed under additin and subtraction, (hf)/d must be an integer, d must divide hf.

Given that gcd (f,d) = 1 from above, d must divide h and h/d must be an integer

so ...

#### Solution Summary

Congruences, Primes, Inverse Modulo, GCD and Wilson's theorem are investigated. The solution is detailed and well presented. The response received a rating of "5" from the student who originally posted the question.