# Find last two digits of $302^{46}$

I need to find the last two digits of $$302^{46}$$ without resorting to Euler's theorem or Chinese remainder theorem (they have not been introduce so far in the course; I can user Fermat's little theorem though). This is what I tried:

We have to work $$\pmod{100}$$ and it is easy to see that:

$$302 = 2 \pmod{100}$$

So I can write

$$302^{46} = 2^{46} \pmod{100}$$

I'm stuck here I don't know know to further reduce $$2^{46}$$.

• $2^{10} = 1024$, so $2^{40} = (2^{10})^4 = 24^4$(mod 100) and then multiply by $2^6$. Use your calculator... – Adam Rubinson Aug 26 '20 at 11:03
• If you don't want to use your calculator, come with $2^{12}$ instead of $2^{10}$. Because $2^{12} = -4$ so the calculations are easier. – TheSilverDoe Aug 26 '20 at 11:10
• Yeah I didn't know that $2^{12} = 4096$ off the top of my head. Good one. I only have $2^{10} = 1024$ in my brain memory bank. – Adam Rubinson Aug 26 '20 at 11:14
• @AdamRubinson It is useful, especially when dabbling with computer science as well, to know up to about $2^{20}$, when it approximates a million (more exactly $1048576$ from memory). – Deepak Aug 26 '20 at 11:19
• Oof, I have too much to remember already. And I haven't had to use that in CS yet, but maybe if it becomes useful to know for me then I will learn it. – Adam Rubinson Aug 26 '20 at 11:22

So you wanna calculate $$2^{46}$$ modulo $$100$$. For that note that $$2^{46}=(2^{20}\times 2^{3})^2=((2^{10})^2\times 8)^2=(24^2\times 8)^2=(76\times 8)^2=(8)^2=64$$in $$\mathbb Z/100\mathbb Z$$. Thus, $$2^{46}\equiv 64\pmod{100}$$.

• where does 76 come from? – Michaelangelo Meucci Aug 26 '20 at 11:16
• Haha this method is great. – Adam Rubinson Aug 26 '20 at 11:19
• @MichaelangeloMeucci $24^2=576$ and so in modulo $100$, its equal to $76$. – Anand Aug 26 '20 at 11:20

$$302^{46} = 2^{46} = (2^{12})^3 \times 2^{10} = (-4)^3 \times 24 = -64 \times 24 = 64 \quad $$

$$2^{10} = 1024$$, so $$2^{40} = (2^{10})^4 = 24^4$$(mod 100).

Hence, $$2^{46} = 24^4 \times 2^6$$ = $$21233664$$ (mod $$100$$) = $$64$$

HINT

$$a^n \equiv(a\pmod{m})^{(n \pmod{\phi(m})}\pmod{m}$$

where $$\phi(100) = 100*(\frac{1}{2})*(\frac{4}{5})$$ , a = 2 ; n = 46; m =100;

SO you will get $$2^{46} \equiv(2^{6})$$

• I cannot use that as stated in the question – Michaelangelo Meucci Aug 26 '20 at 11:20
• I don't know brother why your question has this limitation. But it's none other than generalization of Fermat's little theorem. Hope without limitation this method will help u. – Jr.Green Aug 26 '20 at 11:22
• Note: $2^{41}\not\equiv 2^1\bmod100$ – J. W. Tanner Aug 26 '20 at 11:38
• That rule you gave applies when $a$ and $n$ are relatively prime, and that's not the case in this problem – J. W. Tanner Aug 26 '20 at 21:13
• @J.W.Tanner I think, for that case the formula is $a^n \equiv(a\pmod{p})^{(n \pmod{(p-1})}\pmod{p}$ – Jr.Green Aug 27 '20 at 5:54

Quite an efficient way of raising numbers to high powers modulo another number is squaring method. See: https://en.m.wikipedia.org/wiki/Exponentiation_by_squaring . It essentially boils down to taking the binary representation of the exponent. In our case, $$46=(101110)_2$$ and you proceed by calculating $$2^n\pmod{100}$$ where $$n$$ in binary representation is the initial segment of the binary representation of the exponent (i.e. we will do it for $$1=1_2, 2=10_2, 5=101_2, 11=1011_2, 23=10111_2, 46=101110_2$$, in that order):

$$2^1\equiv 2\pmod{100}$$ $$2^2=(2^1)^2\equiv 2^2=4\pmod{100}$$ $$2^5=(2^2)^2\cdot 2\equiv 4^2\cdot 2=32\pmod{100}$$ $$2^{11}=(2^5)^2\cdot 2\equiv 32^2\cdot 2=2048\equiv 48\pmod{100}$$ $$2^{23}=(2^{11})^2\cdot 2\equiv 48^2\cdot 2=4608\equiv 8\pmod{100}$$ $$2^{46}=(2^{23})^2\equiv 8^2=64\pmod{100}$$

$$\!\bmod 25\!:\ 2^{\large10}\! = 1024 = -1\,\overset{(\ \ )^{\Large 4}\!}\Rightarrow\ 2^{\large 40}\!\equiv 1$$ $$\,\Rightarrow\, 1 = 2^{\large 40}\!+25j\,\overset{\large \times\,2^{\Large 6}}\Longrightarrow\, 2^{\large 6} = 2^{\large 46}\!+\color{#c00}{100}(2^{\large 4}j)$$

Remark  This can be done more operationally using the $$\!\bmod\!$$ Distributive Law as follows

$$2^{\large 46}\bmod 100\, =\, 2^{\large 2}(2^{\large 4}\underbrace{(2^{\large 10}}_{\large \equiv\, -1})^{\large 4}\bmod 25)\, =\, 2^{\large 2}(2^{\large 4})\qquad$$

• Uses only trivial arithmetic: $\ (-1)^{\large 4} = 1,\,$ and $\ 2^{\large 2}\cdot 25 = \color{#c00}{100}.\$ The final scaling is better done in congruence language if that result is known. – Bill Dubuque Aug 26 '20 at 15:39

Consider the multiplicative semigroup contained in $$\mathbb {Z} / \text{100} \mathbb {Z}$$.

Using the table we see that

$$\quad 16^5 = 76 \pmod{100}$$

So

$$\quad 2^{46} = 4 \, (2^4)^{11} \equiv 4 \, (16)^{11} \equiv 4 \cdot 16 \cdot (76 \cdot 76) \equiv 4 \cdot (16 \cdot 76) \equiv 4 \cdot 16 \equiv 64 \pmod{100}$$

For more details on this technique/theory, see this.