(See attached file for full problem description)
Conjecture: Suppose that m and n are positive integers. If gcd(m,n)=1, then .
a. If m and n are positive integers and k is any integer, show that gcd(k,mn)=1 if and only if gcd(k,m)=1 and gcd(k,n)=1.
b. Suppose gcd(m,n)=1. Prove that establishes a bijection between and . (In other words, if f(k)=(a,b), then gcd(k,mn)=1 if and only if gcd(a,m)=1 and gcd(b,n)=1)
c. Use the results of the preceeding two exercises to complete the proof of the conjecture.
NOTE: In this discussion will be the function defined in the chapter summary for the Chinese Remainder Theorem given by .© BrainMass Inc. brainmass.com October 9, 2019, 6:22 pm ad1c9bdddf
Please see the attachment.
(a) If , then we can find two integers , such that . This means , .
Conversely, if , , then I claim that . If not, we can find a prime factor of ...
This solution is comprised of a detailed explanation to show that gcd(k,mn)=1 if and only if gcd(k,m)=1 and gcd(k,n)=1.