Results 1 to 6 of 6

Thread: Proof about Euler's φ-function

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    58

    Proof about Euler's φ-function

    Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

    I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    In general is...

    $\displaystyle \displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

    ... so that if m and n have no common prime factors is...

    $\displaystyle \displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n)$ (2)

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by page929 View Post
    Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

    I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.
    I assume your [a]m was supposed to be [b]m? I think the hint is almost a proof in itself! Where are you stuck?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by chisigma View Post
    In general is...

    $\displaystyle \displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)



    I don't think they can use this...in fact, as far as I remember, to reach this formula one must first know the multiplicativity of $\displaystyle \phi$ and its values on powers of primes.
    If they ould use this formula the question would be utterly trivial

    Tonio


    ... so that if m and n have no common prime factors is...

    $\displaystyle \displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n)$ (2)

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    In ...

    Totient Function -- from Wolfram MathWorld

    ... is written the following precedure...

    ... the 'fundamental theorem of arythmetic' extablishes that any integer $\displaystyle m>1$ is represented as the product...

    $\displaystyle \displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}}$ (1)

    ... where $\displaystyle p_{k} , k=1,2,...,r$ are the r distincts primes deviding m. If $\displaystyle m= p^{\alpha}$ the numbers of factors relatively prime to m is...

    $\displaystyle \displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p})$ (2)

    If $\displaystyle m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}$ the numbers of factors relative prime to m is...

    $\displaystyle \displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\ (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}})$ (3)

    Proceeding by induction we arrive at the formula...

    $\displaystyle \displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}})$ (4)

    It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis, so that the formula valid for m and n coprimes...

    $\displaystyle \varphi(m\ n) = \varphi (m)\ \varphi (n)$ (5)

    ... is derived from (4) and not viceversa...

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by chisigma View Post
    In ...

    Totient Function -- from Wolfram MathWorld

    ... is written the following precedure...

    ... the 'fundamental theorem of arythmetic' extablishes that any integer $\displaystyle m>1$ is represented as the product...

    $\displaystyle \displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}}$ (1)

    ... where $\displaystyle p_{k} , k=1,2,...,r$ are the r distincts primes deviding m. If $\displaystyle m= p^{\alpha}$ the numbers of factors relatively prime to m is...

    $\displaystyle \displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p})$ (2)

    If $\displaystyle m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}$ the numbers of factors relative prime to m is...

    $\displaystyle \displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\ (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}})$ (3)

    Proceeding by induction we arrive at the formula...

    $\displaystyle \displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}})$ (4)

    It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis


    This is interesting and I wasn't aware of it, but it isn't completely accurate: only in point (13) arrives Wolfram to the formula, after having used induction and, in (6)-(7)-(8) using a not so straightforward deduction on different primes dividing a given natural number n.

    Anyway, is another way to approach this.

    Tonio


    , so that the formula valid for m and n coprimes...

    $\displaystyle \varphi(m\ n) = \varphi (m)\ \varphi (n)$ (5)

    ... is derived from (4) and not viceversa...

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler function proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jul 23rd 2011, 08:44 AM
  2. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 5th 2011, 12:04 AM
  3. [SOLVED] Can someone help with a proof involving Euler's phi function?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 27th 2010, 09:25 PM
  4. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 7th 2010, 08:46 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 29th 2009, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum