Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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} $. –  Dan Douglas yesterday
    
Unless the answer is 1, of course. That must be what happens then. –  Dan Douglas yesterday

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.