quickest way to find remainder for
$\LARGE \begin{align} \color{black}{
\dfrac{65^{{37}^{80}}}{39} \hspace{.33em}\~\
}\end{align}$

Question

quickest way to find remainder for
$\LARGE  \begin{align} \color{black}{
\dfrac{65^{{37}^{80}}}{39} \hspace{.33em}\~\
}\end{align}$

ikram002p · Answer

waitiiiing :D

ikram002p · Answer

are you gonna show answer or should i try ?

mathmath333 · Answer

my method was long , so i want quickest (lazy) way

ikram002p · Answer

$\Large  \begin{align*}
65 &\equiv 26 \mod 39 \ 
 65^{37^{80}}  &\equiv    26 ^{37^{80}}\mod 39 \ \text{now note this }  \ 
26^{\phi(39)} &\equiv 1 \mod 39\ 
 26^{24}&\equiv  1 \mod 39 \ 
  26^{24 n}&\equiv  1^n \mod 39 \ 
 26^{24 n+q}&\equiv  1\times 26^q \mod 39 \ 
 26^{24 n+q}&\equiv   26^q \mod 39 \ \text { so we need to know q}\


37^{80} \mod 24 &\equiv q \mod 24 \ 

37^{80}&\equiv 13^{80} \mod 24 \


13^{\phi(24)}&\equiv 1 \mod 24 \

13^{8}&\equiv 1 \mod 24 \
13^{80}&\equiv 1 \mod 24 \

\text{thus } q=1 \

\end{align*} $

ikram002p · Answer

by understanding that relation then you can quick reach this result :-

$\Large \begin{align*}

65^{37^{80}} &\equiv   26^{37^{80}}\mod 39\ 
 &\equiv   26^{({37^{80}\mod 24})}\mod 39 \ 
 &\equiv  26^{1}\mod 39\ 
 &\equiv  26 \mod 39
\end{align*}
$

mathmath333 · Answer

$\Large \begin{align} \color{black}{\normalsize \text{chinese remainder theorm}\hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{39} \hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{39}=3r_2x+13r_1y \hspace{.33em}\~\
3x+13y=1\hspace{.33em}\~\
x=-4,y=1\hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{39}=-12r_2+13r_1 \hspace{.33em}\~\
39=13\times 3 \hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{3}=r_1 \hspace{.33em}\~\
=\dfrac{(3\times 22-1)^{{37}^{80}}}{3}\hspace{.33em}\~\
=\dfrac{(-1)^{{37}^{80}}}{3}\hspace{.33em}\~\
=\dfrac{(-1)^{odd}}{3}\hspace{.33em}\~\
=\dfrac{-1}{3}\hspace{.33em}\~\
=\dfrac{2}{3}\hspace{.33em}\~\
=2\hspace{.33em}\~\
\fbox{r_1=2 }\hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{13}=r_2 \hspace{.33em}\~\
=\dfrac{(13\times 5)^{{37}^{80}}}{13}\hspace{.33em}\~\
=\dfrac{(0)^{{37}^{80}}}{13}\hspace{.33em}\~\
=0\hspace{.33em}\~\
\fbox{r_2=0 }\hspace{.33em}\~\
\dfrac{65^{{37}^{80}}}{39}=-12(0)+13(2)=\LARGE 26 \hspace{.33em}\~\


}\end{align}$

ikram002p · Answer

hmm interesting :)

mathmath333 · Answer

Yes but it seems little  longer...

mathmath333 · Answer

it works in case the divisors are composite

ikram002p · Answer

meybe you wanna have a look @ganeshie8

ganeshie8 · Answer

ikram's method looks more simpler..

ganeshie8 · Answer

chinese remainder thm looks fancy and interesting xD

mathmath333 · Answer

yes but its still like bolt from the blue for me

ikram002p · Answer

he asked for quick :O

ganeshie8 · Answer

she is using only one thm :  euler generalizatio to fermat's little thm

ikram002p · Answer

i can solve using Eclids algorithm without caring how much its gonna take time

ganeshie8 · Answer

you must be knowing fermat's little thm for prime moduli :  
$$a^{p-1}\equiv 1\pmod{p}$$

?

mathmath333 · Answer

yes it quick compared to the chineese.

mathmath333 · Answer

yes

ganeshie8 · Answer

Notice fermat's little thm only works for prime moduli
euler's generalization is a nice extension to fermat's little thm

ganeshie8 · Answer

eulero's generalization :  
$$a^{\phi(n)}\equiv 1\pmod{n}$$

here $n$ could be any integer

ganeshie8 · Answer

(any $n$ relatively prime to $a$ )

ikram002p · Answer

hehe exactly :P

mathmath333 · Answer

yes i learnt that

$\phi(n)=n(1-1/p_1)(1-1/p_1).....(1-1/p_n)$

where p1,p2...pn are prime factors

ganeshie8 · Answer

$\phi(n)$ is a very friendly function  which you can compute easily w/o any formulas

ganeshie8 · Answer

$\phi(n)$ gives the number of positive integers that are less than $n$ and relatively prime to $n$

mathmath333 · Answer

for euler method a and n must be co prime ?

ganeshie8 · Answer

yes

ganeshie8 · Answer

lets do an example of phi function maybe ?

mathmath333 · Answer

yes

ganeshie8 · Answer

$\phi(6) = 2$ 

because  there are exactly $2$ positive integers less than $6$ that are relatively prime to $6$ :  $ \{1, 5\}$

ganeshie8 · Answer

$\phi(7) = ?$

mathmath333 · Answer

6

ganeshie8 · Answer

because every positive integer less tha a prime is relatively prime

mathmath333 · Answer

7(1-1/7)=6

ganeshie8 · Answer

that formula works 
notice also $\phi(p) = p-1$

mathmath333 · Answer

its for prime $p$

ganeshie8 · Answer

yes

mathmath333 · Answer

then it becomes fermat

ganeshie8 · Answer

Exactly! lets see if we can work below problem using euler thm : 

find the remainder when $35^{401}$ is divided by $12$

ganeshie8 · Answer

in other words, reduce  below : 
$$x\equiv   35^{401} \pmod{12}$$

mathmath333 · Answer

$\dfrac{(-1)^{401}}{12}=11$

ganeshie8 · Answer

Very smart :) thats a bad example haha let me cook a harder one lol

ganeshie8 · Answer

$$x\equiv   41^{401} \pmod{12}$$

mathmath333 · Answer

w8

ganeshie8 · Answer

kk try to use euler thm

mathmath333 · Answer

$\Large \dfrac{41^{401}}{12}\
=\dfrac{5^{401}}{12}\
=\dfrac{5\cdot 5^{400}}{12}\
=\dfrac{5\cdot 25^{200}}{12}\
=\dfrac{5\cdot 1^{200}}{12}\
=5
$

mathmath333 · Answer

oh euler

ganeshie8 · Answer

thats clever lol

ganeshie8 · Answer

euler is not needed for working that
but you may use it just to get some practice

mathmath333 · Answer

i was having difficulty for this type 
$\Large  a^{b^c}$

mathmath333 · Answer

may be i need more practice with euler. thnks

ganeshie8 · Answer

$\phi(12) = 4$ so euler gives us $41^{4}\equiv 1 \pmod{12}$

thats the end of euler,  we simply use that to reduce the power

ganeshie8 · Answer

$$41^{401} \equiv     41(41^{400}) \equiv  41(41^4)^{100}\equiv  41(1)^{100}\equiv 41 \equiv 5 \pmod{12}$$