4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ $2^{10} = 1024$, so $2^{40} = (2^{10})^4 = 24^4$(mod 100) and then multiply by $2^6$. Use your calculator... $\endgroup$ – Adam Rubinson Aug 26 '20 at 11:03
  • $\begingroup$ 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. $\endgroup$ – TheSilverDoe Aug 26 '20 at 11:10
  • $\begingroup$ 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. $\endgroup$ – Adam Rubinson Aug 26 '20 at 11:14
  • $\begingroup$ @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). $\endgroup$ – Deepak Aug 26 '20 at 11:19
  • $\begingroup$ 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. $\endgroup$ – Adam Rubinson Aug 26 '20 at 11:22
3
$\begingroup$

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

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

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I cannot use that as stated in the question $\endgroup$ – Michaelangelo Meucci Aug 26 '20 at 11:20
  • $\begingroup$ 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. $\endgroup$ – Jr.Green Aug 26 '20 at 11:22
  • 1
    $\begingroup$ Note: $2^{41}\not\equiv 2^1\bmod100$ $\endgroup$ – J. W. Tanner Aug 26 '20 at 11:38
  • $\begingroup$ That rule you gave applies when $a$ and $n$ are relatively prime, and that's not the case in this problem $\endgroup$ – J. W. Tanner Aug 26 '20 at 21:13
  • $\begingroup$ @J.W.Tanner I think, for that case the formula is $a^n \equiv(a\pmod{p})^{(n \pmod{(p-1})}\pmod{p}$ $\endgroup$ – Jr.Green Aug 27 '20 at 5:54
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Aug 26 '20 at 15:39
0
$\begingroup$

Consider the multiplicative semigroup

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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