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