# Proving Multiplicativity of $\phi$ Using Euler's Theorem

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)?$$

• 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. – Qiaochu Yuan Mar 2 '12 at 20:51
• Use \pmod{x} to produce the parenthesis, roman typeface, and appropriately spaced $\pmod{x}$. – Arturo Magidin Mar 2 '12 at 20:51
• 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. – Arturo Magidin Mar 2 '12 at 20:54
• 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! – wjm Mar 2 '12 at 20:58
• (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? – Arturo Magidin Mar 2 '12 at 21:01

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.

• The Carmichael formula is incorrect (terrible twos ... $2$ is an odd prime) – Bill Dubuque Mar 2 '12 at 22:49
• @Bill Dubuque: Thanks! The oddest prime has been dealt with. – André Nicolas Mar 2 '12 at 23:13

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.

• 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}$. – Jakub Konieczny Mar 2 '12 at 20:50

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

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)$$