Explore BrainMass

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

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

https://brainmass.com/math/basic-algebra/congruences-primes-inverse-modulo-gcd-and-wilson-s-theorem-42377

#### 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)