Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}$.
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}$.
$$302^{46} = 2^{46} = (2^{12})^3 \times 2^{10} = (-4)^3 \times 24 = -64 \times 24 = 64 \quad [100]$$
$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$$
HINT
use the tontient function instead.
$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})$
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}$
