Explore BrainMass

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.