1. ## [SOLVED] Two questions about Euler

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

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

3. ## Thx

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