4. (a) (4 pts) Show that if p.q are distinct odd primes and n - with2 1, then th

Question

4. (a) (4 pts) Show that if p.q are distinct odd primes and n - with2 1, then the congruence 2 1 (mod n) has exactly 4 solutions. Show that these four solutions arel, ta (mod n) for some a f t1 (mod n). Hint: You will find the conclusion of problem 3. useful as well as one of theorems from Section 5 (b) (4 pts) With n as in part (a), let fri,r2....,r(n)) be the set of least residues (mod n) that are relatively prime to n. Show that irn) 1 (mod n). Hint: This can be done by modifying the first half of the proof of Wilson's theorem and using (a).

Explanation / Answer

use preposition -

If a ? b (mod m) and a ? b (mod n) with gcd(m, n) = 1 then a ? b (mod mn).

Lemma-If gcd(a, n) = 1 then {r1, r2, . . . , rn} is a complete residue system modulo n if and only if {ar1, ar2, . . . , arn} is also a complete residue system modulo n

Proof_

By the above Proposition ar_j ? ar_k (mod n) implies r_j ? r_k (mod n) if gcd(a, n) = 1, in which case {ar1, ar2, . . . , arn} represents distinct congruence classes modulo n if and only if {r1, r2, . . . , rn} also represents distinct congruence classes modulo n.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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