Suppose that p and q are distinct with p congruent to q congruent to -1 (mod 4),

Question

Suppose that p and q are distinct with p congruent to q congruent to -1 (mod 4), and let x & y be elements of Z*_n with x^2 congruent to y^2 (mod n) and (x/n) not equal to (y/n). Prove that gcd(x-y, n) = p or q.

Explanation / Answer

The MOD operator is defined such that 0 x divides y + z......... x divides y - (y MOD z)....................... The congruence operator == is defined such that x == y (mod z) z divides (x - y) ..... or equivalently x == y (mod z) x MOD z = y MOD z................... z == 0 (mod z).................. x == y (mod z) ==> y == x (mod z).................. x == y (mod z) and y == t (mod z) ==> x == t (mod z)................ x1 == x2 (mod z) and y1 == y2 (mod z) ==> x1 + y1 == x2 + y2 and.............. x1 - y1 == x2 - y2 and x1 * y2 == x2 * y2........ Thus you can add, subtract, and multiply congruences. GCD(a,b)=c means c>=0, c|a and c|b. Furthermore, every integer d that divides a and b also divides c. To put it another way, here are the properties of GCD, in a nutshell -- this form is useful for proofs, because it provides a checklist of things you must show in order to establish GCD(a,b) as well as a set of facts you know if you know GCD(a,b): GCD(a,b)>=0 GCD(a,b)|a GCD(a,b)|b if integer d exists such that d|a and d|b then d|GCD(a,b) That last item in the checklist is equivalent to the following statement: for all integers d, it is true that d-|a or d-|b or d|GCD(a,b) Cancellation Rule m * p == m * q (mod n) and GCD(m,n) = 1 ==> p == q (mod n) Thus m can safely be cancelled mod n so long as GCD(m,n) = 1. Prime Numbers .............. An integer p is a prime number if and only if p > 1 and {x : x divides p} = {1, p} ................ If p and q are both prime and p divides q, then p = q. If p is prime and p does not divide n then GCD(p,n) = 1. If p is prime and p divides n*m then p must divide either n or m (or both). Any integer n can be factorized uniquely into the product of a list of primes p1 * p2 * ...

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.