[SOLVED] Two questions about Euler

**KenMarston** · April 16th 2009, 07:59 PM

find $3^{51204}$ ( $\bmod 74800$ )

i got $\phi(74800)$ = 29760 & (3,74800) =1
so, $3^{\phi(74800)}$ $\equiv 1$ ( $\bmod 74800$ )
but what shall i do next? 51204-29760 = 21444, it's still a big number.

2. find all n such that $\phi(n)$ = 6.
i really have no idea about this one.
i try $\phi(X) = \phi(m) \phi(n)$ where (m.n) = 1 & $\Sigma(\phi(d) )$ = m where d|m. but got nothing usefull.

any help will be appreciated.

**PaulRS** · April 17th 2009, 07:07 AM

1) Note that: $ 74800 = 2^4 \cdot 5^2 \cdot 11^1 \cdot 17^1 $

Now by Euler's Theorem, separately: $ \left\{ \begin{gathered} 3^{\phi \left( {2^4 } \right)} \equiv 1\left( {\bmod .2^4 } \right) \hfill \\ 3^{\phi \left( {5^2 } \right)} \equiv 1\left( {\bmod .5^2 } \right) \hfill \\ 3^{\phi \left( {11^1 } \right)} \equiv 1\left( {\bmod .11^1 } \right) \hfill \\ 3^{\phi \left( {17^1 } \right)} \equiv 1\left( {\bmod .17^1 } \right) \hfill \\ \end{gathered} \right. $ (*)

Consider $ \rho = {\text{lcm}}\left( {\phi \left( {2^4 } \right);...;\phi \left( {17^1 } \right)} \right) = 80 $ (least common multiple). THis number satisfies $ \left\{ \begin{gathered} 3^\rho \equiv 1\left( {\bmod .2^4 } \right) \hfill \\ 3^\rho \equiv 1\left( {\bmod .5^2 } \right) \hfill \\ 3^\rho \equiv 1\left( {\bmod .11^1 } \right) \hfill \\ 3^\rho \equiv 1\left( {\bmod .17^1 } \right) \hfill \\ \end{gathered} \right. $ by using (*) and knowing that $\rho$ is multiple of each of the exponents there.

That is: $ \left\{ \begin{gathered} 2^4 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\ 5^2 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\ 11^1 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\ 17^1 \left| {\left( {3^\rho - 1} \right)} \right. \hfill \\ \end{gathered} \right. $ now since each of the divisors on the LHS are coprime to each other this implies that the product of them divides $ {\left( {3^\rho - 1} \right)} $ that is: $ 74800\left| {\left( {3^\rho - 1} \right)} \right. $

So we have: $ 3^{80} \equiv 1\left( {\bmod .74800} \right) $ and $ 51204 \equiv 4\left( {\bmod .80} \right) $ thus $ 3^{51204} \equiv 3^4 \left( {\bmod .74800} \right) $

2) Remember that $ \phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1} {p}} \right)} =6 $ ( the product goes over the prime numbers dividing n)

Then we may write: $ \frac{n} {{\prod\limits_{\left. p \right|n} p }} = \frac{6} {{\prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} }} $ (1)

So that: $ \left. {\prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} } \right|6 $ (2) now if: $ p > 2 \Rightarrow 2\left| {\left( {p - 1} \right)} \right. $ and since $4\not|6$ it follows that $n$ can have at most one odd prime divisor.

Thus: $ n = 2^\alpha \cdot q^{\beta} $ where $q$ is an odd prime

If $\beta>0$ then our (2) turns into $ \left. {\left( {q - 1} \right)} \right|6 $ thus: $ q = 3 \vee q = 7 $

Consider firsrt $\alpha>0$

The LHS of (1) is: $ 2^{\alpha - 1} \cdot q^{\beta - 1} $ if (see (1) ) $ q = 7 \Rightarrow 2^{\alpha - 1} \cdot 7^{\beta - 1} = 1 \Rightarrow \alpha = \beta = 1 $ and if $ q = 3 \Rightarrow 2^{\alpha - 1} \cdot 3^{\beta - 1} = 3 \Rightarrow \alpha = 1 \wedge \beta = 2 $

So we have got the solutions $ n = 14;n = 18 $

If $\alpha=0$ then $ \Rightarrow \phi \left( n \right) = \left( {q - 1} \right) \cdot q^{\beta - 1} = 6 $ and so either $\beta=1$ and then $n=7$ or $\beta>1$ and so $q=3$ (since q|6) and then $n=9$

It remains to check what happens when n is a power of 2. In this case (1) turns into $ 2^{\alpha - 1} = 6 $ which is impossible. ANd so we have all the possible solutions

**KenMarston** · April 18th 2009, 05:47 PM

thx~~u really help me a lot~
besides, i want to add that, the 1st one should be more easier~~
i din't notice that 187 = 11 x 17~ToT~
since $\phi(74800) = \phi (5^2) * \phi(2^4) * \phi(17) * \phi(11) = 25600$
and $3^{\phi(74800)} = 3^{25600} \equiv1(\bmod 74800)$
$51204 \equiv 4( \bmod 25600)$
so, $3^{51204} \equiv 3^4(\bmod 74800)$

Thread: [SOLVED] Two questions about Euler

LinkBack

Thread Tools

Display

[SOLVED] Two questions about Euler

Thx

Similar Math Help Forum Discussions

a few questions on (Z/nZ)* and Euler's Totient Function

Euler's Theorem Questions

[SOLVED] Euler Method

ODE solved using Euler's equation

[SOLVED] Euler Expression

Search Tags