# 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... Aug 26, 2020 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. Aug 26, 2020 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. Aug 26, 2020 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). Aug 26, 2020 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. Aug 26, 2020 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? Aug 26, 2020 at 11:16
• Haha this method is great. Aug 26, 2020 at 11:19
• @MichaelangeloMeucci $24^2=576$ and so in modulo $100$, its equal to $76$. Aug 26, 2020 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$$

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. Aug 26, 2020 at 15:39

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 Aug 26, 2020 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. Aug 26, 2020 at 11:22
• Note: $2^{41}\not\equiv 2^1\bmod100$ Aug 26, 2020 at 11:38
• That rule you gave applies when $a$ and $n$ are relatively prime, and that's not the case in this problem Aug 26, 2020 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}$ Aug 27, 2020 at 5:54

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.

$$2^{46} \equiv 4^{23} \equiv 4 \cdot 4^{22} \equiv 4 \cdot 16^{11} \equiv 4 \cdot 16 \cdot 16^{10} \equiv 4 \cdot 16 \cdot 56^{5} \equiv$$
$$\quad 4 \cdot 16 \cdot 56 \cdot 56^{4} \equiv 4 \cdot 16 \cdot 56 \cdot 36^{2} \equiv$$
$$\quad 4 \cdot 16 \cdot 56 \cdot 96 \equiv^\text{algorithm complete / now applying discretionary techniques}$$
$$\quad 4 \cdot 16 \cdot 56 \cdot (-4) \equiv (-1) \cdot 4\cdot 4 \cdot 16 \cdot 56 \equiv (-1) \cdot 16 \cdot 16 \cdot 56 \equiv$$
$$\quad (-1) \cdot 56 \cdot 56 \equiv -36 \equiv 64 \pmod{100}$$