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$ Aug 26, 2020 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$ Aug 26, 2020 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$ Aug 26, 2020 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, 2020 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$ Aug 26, 2020 at 11:22

8 Answers 8

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

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$ Aug 26, 2020 at 15:39
0
$\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$ Aug 26, 2020 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, 2020 at 11:22
  • 1
    $\begingroup$ Note: $2^{41}\not\equiv 2^1\bmod100$ $\endgroup$ Aug 26, 2020 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$ Aug 26, 2020 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, 2020 at 5:54
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$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .