# Euler Function

(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 ad1c9bdddfhttps://brainmass.com/math/graphs-and-functions/euler-function-86510

#### Solution Preview

Please see the attachment.

Proof:

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

#### Solution Summary

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.