# how to solve these questions with congruences

how can I solve these type of questions : using congruences

find the last digit or last two digit of $27^{27^{26}}$ and find remainder when $53^{103}$ is divided by 7.

I can solve 2nd question and a simpler case of first question with binomial theorem but in questions like 1st this does not seem to work for me, and using binomial makes the solution too lengthy so as I see I have only left congruence method but I do not know how to initiate the solution .

I have burton's book of number theory in which there are some examples and exercises for questions like this but still I am not able to catch the pattern these queations should follow to be solved by congruences ,
I would really appreciate any advice or suggestions or anything that can help me to solve these questions

-

By Euler's totient theorem, we know

$$27^{\phi(100)}=27^{40}\equiv 1 \rm{mod} 100,$$ On the other hand, $$27^{\phi(40)}=27^{16}\equiv 1 \rm{mod} 40,$$ so we have $27^{26}\equiv 27^{10}\equiv 3^{30}\equiv 3^{4\times7}\cdot9\rm{mod}40\equiv 9 \rm{mod}$. Hence we have $$27^{27^{26}}\equiv27^{40n+9}\equiv 27^9\rm{mod} 100=3^{27}\rm{mod} 100$$ Which is not difficult to conclude the answer 87.

-
how to calculate $3^{27}(mod\ 100)$ after $3^{40}≡1(mod\ 100)$ by Euler's totient theorem as $\phi(100)=40$ – lab bhattacharjee Aug 20 '12 at 10:35
I didn't use Euler's totient theorem there. As you suggested, we can use $3^{20}\equiv 1 {\rm{mod}}\,100$. I calculate $27^9(\rm{mod}\, 100)$ instead as follows: $27^9=(20+7)^9\equiv 9\times 7^8\times 20+7^9\equiv 80+7\equiv 87 {\rm{mod}} \,100$, since $7^4\equiv 1{\rm{mod}}\,100$. – Y.Z Aug 20 '12 at 11:50

To find the last two digits of $27^{27^{26}}$, you can first deal with the exponent of 27, namely $27^{26}$. First, consider $27^1$. This is congruent to 27 (mod 100). We use mod 100 in order to get the last two digits as this gives us the last two digits of the representation in base 10.

Now, find that $27^2$=729, which is congruent to 29 (mod 100). Use the fact that if $a\equiv{b}$ (mod c), then $a^k$$\equiv{b^k}$ (mod c). This means that $27^4\equiv{29^2}$ (mod 100). You can repeat this process in order to quickly find the congruences for all powers of 27 that are powers of two. Then multiply together the appropriate ones to find $27^{26}$ (mod 100). In this case, you will need to multiply what you find to be the congruences for $27^2$, $27^8$, and $27^{16}$, since 2+8+16=26. Reduce this mod 100. Note that this uses the fact that if $a\equiv{b}$ (mod m) and if $c\equiv{d}$ (mod m), then $ac\equiv{bd}$ (mod m). So, we now know the last two digits of $27^{26}$. Say they are $xy$. Then, to find the last two digits of $27^{27^{26}}$, do this process again, this time considering $27^{100k+xy}$=$(27^{100})^k*27^{xy}$. The first part requires that you find the modulo of $27^{100}$ (the $k$ can be ignored as this doesn't change the value). The second part also requires the original method again. Then multiply their modulos and reduce mod 100 again if necessary

FYI, the last two digits are 87.

-
Thanks to the answer of lab bhattacharjee for helping me fix and understand an error in my original answer. – C. Williamson Aug 18 '12 at 8:06
I do not understand why you say the $k$ can be ignored. As an example, $2^3 \equiv 2 \pmod {3}$ whereas $(2^3)^2 \equiv 1 \pmod {3}$. – Doug Aug 18 '14 at 19:25
Unless the answer is 1, of course. That must be what happens then. – Doug Aug 18 '14 at 19:28

$27^{27^{26}}=(3^3)^{3^{3.26}}=(3^3)^{3^{78}}=3^{3^{79}}$

To find the last digit, we need to take modulo 10.

By Euler's totient theorem, $3^{\phi(10)}≡1(mod\ 10)=>3^4≡1(mod\ 10)$

Now $3^{79}=(4-1)^{78} 3≡3(mod\ 4)=4c+3$ for some integer c.

So, $27^{27^{26}}=3^{3^{79}}=3^{4c+3}=(3^4)^c\cdot 3^3≡1\cdot 27(mod\ 10)≡7(mod\ 10)$

To find the last two digit, we need to take modulo 100.

(1)

(i)Now by Euler's totient theorem, $\phi(4)=2=>3^2≡1(mod\ 4)$ and $\phi(25)=20=>3^{20}≡1(mod\ 25)$

$=>3^{lcm(2,20)}≡1(mod\ 100)=>3^{20}≡1(mod\ 100)$

So, we need find $3^{79}(modulo\ 20)=d$(say)

As $\phi(20)=\phi(5)\phi(4)=4.\cdot 2=8$

So, $3^{8}≡1(modulo\ 20)=>3^{80}≡1=>3(3^{79})≡1=>3d≡1(modulo\ 20)$ as $d=3^{79}(modulo\ 20)$

$=>d≡7(modulo\ 20)=20e+7$(say) for some integer e=>$3^{79}=20e+7$.

$=>27^{27^{26}}=3^{3^{79}}=3^{20e+7}=(3^{20})^e\cdot 3^{7}≡3^7(mod\ 100)=3^6\cdot 3≡29\cdot 3$ (As $3^6=729$)

$≡87(mod\ 100)$

(ii) Alternatively using Carmichael Function , we find that $3^{20}≡1(mod\ 100)$ as $λ(100)=(λ(25),λ(4))=(20,2)=20$.

Rest will be same as (i)

........

(2)

As 100=25*4 where (25, 4)=1 , let us find $3^{3^{79}}(modulo\ 4)$ and $3^{3^{79}}(modulo\ 25)$

As $3^{79}$ is odd , $3^{3^{79}}≡(4-1)^{3^{79}}≡3(mod\ 4)$

As $\phi(25)=20$, we need to find $3^{79}(modulo\ 20)$ which we have already found to be of the form 20e+7.

$3^{3^{79}}(modulo\ 25)=3^{20e+7}=(3^{20})^e\cdot 3^7 ≡3^7(mod\ 25)=(27)^2\cdot 3≡2^2\cdot 3(mod\ 25)≡12(mod\ 25)$

So, we need to find x such that $x≡12(mod\ 25)$ and $x≡3(mod\ 4)$

So, $x=25p+12=4q+3$ for some integers p,q.

Or, $25p=4q-9=4q-(25-6.4)9$

$=>25(p+9)=4(q+54)$

$=>4|(p+9)=>4|(p-3)=>p=4r+3$ for some integer r.

So,$x=25p+12=25(4r+3)+12=100r+87$

-