Explore BrainMass
Share

Explore BrainMass

    Euler Function

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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

    Attachments

    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.

    $2.19