1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler's Totient Function, Proof

  1. Apr 16, 2016 #1
    1. The problem statement, all variables and given/known data
    Suppose m, n are relatively prime. In the problem you will prove the key property of Euler’s function that φ(mn) = φ(m)φ(n).

    (a) Prove that for any a, b, there is an x such that

    x ##\equiv## a (mod m), (1)
    x ##\equiv## b (mod n). (2)

    Hint: Congruence (1) holds iff

    x = jm + a. (3)
    for some j. So there is such an x only if
    jm + a ##\equiv## b (mod n). (4)
    Solve (4) for j.

    (b) Prove that there is an x satisfying the congruences (1) and (2) such that 0 ≤ x < mn.

    (c) Prove that the x satisfying part (b) is unique.

    (d) For an integer k, let k∗ be the integers between 1 and k − 1 that are relatively prime to k. Conclude from part (c) that the function
    f : (mn) ∗ → m∗ × n∗
    defined by
    f(x) ::= (rem(x, m),rem(x, n))

    is a bijection.

    (e) Conclude from the preceding parts of this problem that φ(mn) = φ(m)φ(n).

    2. Relevant equations
    Euler's function given at the top:
    φ(mn) = φ(m)φ(n)

    3. The attempt at a solution
    a) I'm stuck on this first part. Starting by solving (4) for j:
    jm + a ##\equiv## b (mod n).
    jm ##\equiv## b-a (mod n)
    jm = b-a + nl
    for some arbitrary l
    j= ##\frac{b-a+nl}{m}##

    does that constitute solving for j?
    if I plug that into
    x= jm+a
    x= ##\frac{b-a+nl}{m}* m + a##
    ##=b+nl##
    I feel like that's roundabout and doesn't prove that some x exists.
    b) I don't know how to get m and n into a relation involving x, other than what was suggested in part a.

    x= jm+a
    x= ln+b
    but that introduces arbitrary variables that I don't know what to do with.

    Another option I was considering was letting x= mn+a
    so
    mn+a ##\equiv## a (mod m)
    which would be a valid congruency. But I don't know what to do for the other expression
    mn+a ##\equiv## b (mod n)

    I will attempt the later parts after I make some progress on these first two.
     
  2. jcsd
  3. Apr 17, 2016 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    What do you know about the existence of inverses modulo a prime?
     
  4. Apr 17, 2016 #3
    So I looked around and found a very similar problem, with a different hint (note that this variant swaps a,b with m,n).

    part a) For a and b relatively prime,
    ##x \equiv m mod a##
    ##x \equiv n mod b##
    They said to let
    ##b^-1##
    be inverse of
    ##b mod a##
    and ##a-1## be inverse of
    ##a mod b##

    let
    ## x = mbb^-1 + naa^-1##

    which satisfies both congruences.

    ie.

    ## x = mbb^-1 + naa^-1 \equiv m (mod a)##
    ##mbb^-1 \equiv m (mod a)
    That hint leads me down a very different path than the original hint for part a. How did you know that multiplicative inverses were needed?

    b)I'm not sure how to start the second part of the original problem. Do I have to prove that
    ##x \equiv rem(x, ab) mod ab##

    and redefine x as the remainder term?
     
  5. Apr 17, 2016 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    For now, I'm just going to clean up your Latex to make it readable:
    If there is going to be a solution for x in the range 0 to ab-1, what does that suggest about how the solutions are distributed? If a given x is one solution, where might the next solution be?
     
    Last edited: Apr 17, 2016
  6. Apr 18, 2016 #5
    Oh, I'm sorry about messing up the LaTeX. Sorry, I was in a hurry, I'll be sure to double-check in the future.

    If given x is a solution, I would think more solutions can be expressed as x+abk, where k is an arbitrary integer. The abk would be canceled by the modulus operator.
    So then by part a, we know that there is some solution x that is not necessarily in the specified range. Then by adding or subtracting abk for some k, there will certainly be a congruent solution in the range ##0 \leq x\lt ab##
    Otherwise, if some solution x was greater than ab, but the next solution below it is less than 0, this would lead to a contradiction
    ##x\geq ab##
    ##x-ab\lt0##

    c)
    Of the set of solutions that are expressed as
    ##x+akb##
    there can only be one solution in the range of 0 to ab.

    So then we have to account for the possibility that some y, which not congruent to x, is also a solution.
    Say
    ##y \equiv m## (mod a)
    ##y \equiv n## (mod b)
    then by transitivity
    ##y \equiv x## (mod a)
    ##y \equiv x##(mod b)

    so then by the definition of congruency
    ##a \mid (y-x)##
    ##b \mid (y-x)##
    a and b are relatively prime, so the difference (y-x) must contain their prime factorizations with no overlap (Unique Factorization Theorem)
    This means
    ##ab \mid (y-x)##
    which implies
    ##y \equiv x## (mod ab)
    which means it's impossible for the two not to be congruent. They would have the same congruent solution in the range 0 to ab.

    d) I am going to revert back to using the m,n and a,b as stated in the original problem.
    By the Unique Factorization Theorem, a number is relatively prime to mn iff it is relatively prime to both m and n.

    So the function f maps a value x to the pair (x mod m, x mod n)
    By parts b and c, we know that we can select x to be congruent to any (a mod m, b mod n) (in this problem we want a, b not equal to 0.)
    and that this x will be unique (because it is on the limited range 0 to mn-1). So this means the function is a surjection and injection. I don't know how to prove that it is total... I think I'd have to prove the domain and range have the same cardinality, at which point surjection implies total function. How would I go about doing that?

    e) if the function from d) is a bijection, well then
    the cardinality of (mn)* must be equal to the cardinality of (m*)x(n*),
    which is essentially the definition of ##\phi(n)##
     
  7. Apr 18, 2016 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    So would I, but you need to prove it. If x is a solution, show that x+ab is a solution.
    And hence a bijection, no?
     
  8. Apr 18, 2016 #7
    if x is a solution to
    ##x \equiv m ## (mod a)
    ##x \equiv n ## (mod b)

    then x+abk
    ##x+abk \equiv x \equiv m## (mod a)
    ##x+abk \equiv x \equiv n## (mod b)

    I thought you needed to show that a function is surjective, injective and total? Otherwise, couldn't you have something like
    A= (1,2,3)
    B=(4,5)
    f: A -> B
    f(1)=4
    f(2)=5
    with f(3) not mapping onto anything. Isn't this surjective and injective, but not bijective?
     
  9. Apr 19, 2016 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As far as I am aware, a function, not qualified as being partial, is necessarily total. I.e. totality is implied unless specifically stated otherwise.
     
  10. Apr 19, 2016 #9
    I see, thanks. Did the rest of my solution make sense- I mean the parts that you did not specifically address?
     
  11. Apr 19, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, all else looked good.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Euler's Totient Function, Proof
  1. Euler's function (Replies: 1)

  2. Euler function-totient (Replies: 3)

Loading...