Explore BrainMass

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.

    © BrainMass Inc. brainmass.com March 4, 2021, 6:22 pm ad1c9bdddf


    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.