This is a Number Theory question. State and Prove the converse of Lemma 3.4.3. L

Question

This is a Number Theory question. State and Prove the converse of Lemma 3.4.3.

LEMMA 3.4.3 Let p be prime, and let n be an integer. If p does not divide n, then ged( PROOF Let p be prime, and let n be an intger f p does not divide n, then ged(p, ) -1, See Exercise 7 In part b of Example 3, we saw that 234 and 540 are not relatively prime since they share a common factor of 18. However,if we divide both numbers by their ged, we get 264 = 13 18 549-30. 18 =13 and 540 and The resulting integers, 13 and 30, are relatively prime. In general, if two integers are not relatively prime, we can divide them by their ged to create a pair of relativelypr numbers. This fact is expressed in the following lemma. LEMMA 3.4.4 Let a and b be integers that are not both equal to zero, and let d = gcd(a, b). Let x and y be integers such that a = xd and b = yd. Then gcd(x,y) = 1.

Explanation / Answer

if the gcd(p,n)=1 then the greatest common divisor between p and n is 1 which means that there is no integer such that p=n.d (d is integer ) .

so always p/=n.d

hence p does not divide n .

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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