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

Not what you're looking for?

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.

##### Purchase this Solution

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

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

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Probability Quiz

Some questions on probability