3
$\begingroup$

Is it possible to show that $\phi$ is multiplicative using Euler's theorem? That is, can I show

Theorem. Let $m$ and $n$ be relatively prime positive integers. Then $\phi(mn)=\phi(m)\phi(n)$

using

Euler's Theorem. If $m$ is a positive integer and $a$ is an integer with $(a,m)=1$, then $a^{\phi(m)}\equiv1\pmod{m}$?

I have tried a few things, but since they are all congruences, I do not know whether they would be general enough to show this or not.


The idea that I have is the following:

Let $(x,ab)=1$ and $(a,b)=1$. Then $$\begin{align*} x^{\phi(ab)}&\equiv 1\pmod{ab},\\ a^{\phi(b)}&\equiv 1\pmod{b},\\ \text{and }\quad b^{\phi(a)}&\equiv 1\pmod{a}. \end{align*}$$

Taking the logarithms of these expressions, we obtain: $$\begin{align*} \phi(ab) &\equiv 0 \pmod{ab},\\ \phi(b) &\equiv 0 \pmod{b},\\ \text{and }\quad \phi(a)&\equiv 0\pmod{a}. \end{align*}$$

Multiplying the last two expressions by $a$ and $b$, respectively, we obtain:

$$a\phi(b)\equiv0\pmod{ab},\quad \text{and}\quad b\phi(a)\equiv0\pmod{ab},$$ and multiplying these two: $$ab\phi(a)\phi(b)\equiv\phi(a)\phi(b)\equiv0\pmod{ab}.$$ Can I then conclude that since $$\phi(ab)\equiv0\pmod{ab}\text{ and } \phi(a)\phi(b)\equiv0\pmod{ab},$$ then $$\phi(ab)=\phi(a)\phi(b)?$$

  • 0
    What do you mean by "taking logarithms"? And no, it is not. Euler's theorem is still true with $\varphi(n)$ replaced by $2 \varphi(n)$, but $2 \varphi(n)$ is not multiplicative.2012-03-02
  • 0
    Use `\pmod{x}` to produce the parenthesis, roman typeface, and appropriately spaced $\pmod{x}$.2012-03-02
  • 2
    It is *not* true in general that $x^k\equiv 1 \pmod{n}$ implies $k\equiv 0\pmod{n}$. For instance, if $x=1$, then you can take $k=1$ regardless of $n$. It is also not true that $x^k\equiv 1\pmod{n}$ for *all* $x$ relatively prime to $n$ implies $k\equiv 0\pmod{n}$ (or even modulo $\phi(n)$!); for instance, $\phi(8) = 4$, but the group of units modulo $8$ is of exponent $2$, so with $n=8$ and $x$ arbitrary you can take $k=2$, and then $k$ is not equivalent to $0$ either modulo $8$, nor modulo $\phi(8)$. So you cannot "take logarithms" to get the congruences you get.2012-03-02
  • 0
    Then I am totally confused since our professor asked us to prove that $\phi$ is multiplicative "using the Euler's formula" (whatever he meant by that). On a side note, that looks way better! Thanks @ArturoMagidin!2012-03-02
  • 1
    (i) Is there any reason to assume that "Euler's formula" means "Euler's Theorem"? Could it mean the formula that says that if $n=p^a$ with $p$ a prime and $a\gt 0$, then $\phi(n) = (p-1)p^{a-1}$ (or some extensions thereof)? (2) Has your professor suggested anything like the "discrete logarithm" that you are attempting?2012-03-02
  • 0
    To be honest, I have no clue what he means with "Euler's formula." I assumed it would be this theorem since it is the one we have been studying for the past few days. I will ask him to clarify next time I see him. On a side note, we have not seen that one you suggest, @ArturoMagidin.2012-03-02
  • 0
    @Josué Molina: My guess is that the formula the instructor refers to is that if $n=p_1^{e_1}\cdots p_k^{e_k}$ then $\varphi(n)=(p^{e_1}-p^{e_1-1})\cdots (p^{e_k}-p^{e_k-1})$. From this, multiplicativity is essentially immediate. Or maybe it is the equivalent formula $\varphi(n)=n\prod(1-\frac{1}{p_i})$. But the misunderstanding led to an interesting question!2012-03-03

4 Answers 4

3

Define the Carmichael function $\lambda(n)$ as follows. If $n=1$, $2$, or $4$, then $\lambda(n)=\varphi(n)$. If $n>4$ is a power of $2$, then $\lambda(n)=(\varphi(n))/2$. If $n$ is a power of an odd prime, then $\lambda(n)=\varphi(n)$. Finally, if the prime power factorization of $n$ is $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, then $$\lambda(n)=\text{lcm}(\lambda(p_1^{e_1}),\lambda(p_2^{e_2}),\dots, \lambda(p_k^{e_k})).$$

It is easy to verify that $a^{\lambda(n)}\equiv 1\pmod n$ for every $a$ relatively prime to $n$. It is in fact the least positive exponent that has this property for all $a$ relatively prime to $n$. For that reason, $\lambda(n)$ is called the least universal exponent of $n$.

The Carmichael function has, in a natural way, the "Euler's Theorem" property. However, the Carmichael function is not multiplicative. So the Euler's Theorem property is not enough to force multiplicativity.

  • 0
    The Carmichael formula is incorrect (terrible twos ... $2$ is an odd prime)2012-03-02
  • 0
    @Bill Dubuque: Thanks! The oddest prime has been dealt with.2012-03-02
2

I do not think you can take logarithms like that.

For a=2, b=5:

phi(ab)=phi(10)=4 

but your formula claims this should be congruent to 0 modulo ab.

  • 0
    You definitely cannot. As a matter of fact, $a^b \pmod{p}$ (say $p$ is prime for simplicity) tells you a bit about $b$ but _only_ $\pmod{p-1}$.2012-03-02
2

I strongly doubt that you can use Euler's Theorem to significantly simplify the proof of your claim. As you have mentioned, Euler's theorem is about congruences and can hardly give you any useful equalities.

In fact, it is even worse in some sense: note that if you denoted by $\delta_m(a)$ the first such non-zero power $\delta$ that $a^\delta \equiv 1 \pmod{m}$, then Euler basically tells you that $\delta_m(a) | \phi(m)$ (assuming that $\mathrm{gcd}(m,a) = 1$ everywhere).

Note that if you took any function $f$ with positive integer values, and considered $\psi := f \cdot \phi$ then Euler's theorem would also hold for $\psi$ in place of $\phi$, and clearly $\psi$ is not multiplicative for most choices of $f$.

2

Then I am totally confused since our professor asked us to prove that ϕ is multiplicative "using the Euler's formula" (whatever he meant by that).

Probably this means the Euler product formula for $\phi\:$ (below), not the Euler-Fermat theorem. $$\rm \phi(n)\ =\ n\:\prod_{p\ |\ n}\: \left(1-\frac{1}p\right)$$