Finding last 2 digits

Finding last 2 digits of a big power of a number:
For e.g.
1345^73.
From modulo arithmetic we understand that finding last 2 digits is effectively taking mod 100.
And modulo can be applied individually on each term.
So 1345^73 mod 100 = 1345 mod 100 * 1345 mod 100 ... 73 times mod 100

So 
last 2 digits of 1345^73 = last 2 digits of 45^73.

Finding last 2 digits when the unit digit is 1:
Ex1:
11^2
Unit digit will be 1 as we already know.
10s digit will be 10s digit or the base multiplied with unit digit of the power's unit digit.
So here:
1*2 = 2 is the 10s digit.
=> 21 is the last 2 digits of the given number (which we can verify since it's 121).

Ex2:
11^3
Unit digit 1.
10s digit 1*3 = 3
So 31.

Why does it work?

Because any integer that ends in 1 can be written “ 10 a + 1 ” where a is its tens digit.
Modulo 100 we only care about those last two digits, so write

$$N \equiv 10a + 1 \pmod{100}.$$

Now raise this to the k-th power:

$$(10a+1)^{k}= \sum_{i=0}^{k} \binom{k}{i}(10a)^i.$$

Look at the first few terms:

• $i=0$ $\binom{k}{0}(10a)^0 = 1$

• $i=1$ $\binom{k}{1}(10a)^1 = k \cdot 10a$

• $i\ge 2$ Each term has a factor $(10a)^2 = 100a^2$, i.e. a multiple of 100.

Because every term with $i\ge 2$ is already a multiple of 100, they all vanish when we work mod 100.
So

$$(10a+1)^{k} \equiv 1 + k\cdot 10a \pmod{100}.$$

What does that mean for the last two digits?

• Units place – the “1” at the front tells us the units digit is always 1.

• Tens place – the coefficient is $k\cdot 10a$. Multiplying by 10 fixes the 0 in the units spot and puts $k\cdot a$ in the tens spot – but only its last digit matters, because anything beyond that would again be a multiple of 100.

Hence

$$(10a+1)^{k} \equiv 1 + 10\bigl((a \times k)\bmod 10\bigr) \pmod{100}.$$

So the tens digit is simply

$$\bigl(\text{tens digit of the base}\bigr)\times\bigl(\text{units digit of the exponent}\bigr)\pmod{10}.$$

---

Example

• Base: 1921 → last two digits = 21 ⇒ $a = 2$.

• Exponent: 13 → units digit = 3.

Tens digit $= 2 \times 3 \bmod 10 = 6$.
Units digit = 1.

Result: 61, exactly as the trick predicts, because

$$21^{13} \equiv 61 \pmod{100}.$$

That’s all the “mystery”—it’s just the binomial theorem plus the fact that any factor of $10^2$ disappears when you only care about the last two digits.

Ex3:
21^2 = (2*2)1 = 41

Ex4:
31^729 = (3*9)1 = 71

Ex5:
41^223 = (4*3)1 = 21

Ex6:
321^179 = (2*9)1 = 81

Ex7:
61^93 = (6*3)1 = 81
71^87 = (49)1 = 91
341^38 = (4*8)1 = 21


Finding last 2 digits when unit digits are 3,7,9:
Convert the given numbers in such a way that unit digit becomes 1.
3^4 = 81 (cyclicity 4)
7^4 = 2401 (cyclicity 4)
9^2 = 81 (cyclicity 2)

Examples:
79^64 = (79^2)^32 = (6241)^32 = (8)1 = 81
39^5 = (39^2)^2 * 39 = (21)^2 * 39 = 41 * 39 = 1600 - 1 = 99
19^542 = (19^2)^271 = 61^271 = (6)1 = 61
87^5 = (3*29)^5 = 3^5 * 29^5 = 43 * (29^2)^2 * 29 = 43 * 29 * (41)^2 = 43*29*81 = 07
97^144 = (97^2)^72 = (9409)^72 = 9^72 = 81^36 = (48)1 = 81

Finding last 2 digits when unit digit is 5:

If a number ends in 5, every even power ends in 25.

For an odd power, the last two digits are 75 when the tens digit is odd and 25 when the tens digit is even (including the single-digit case 5 itself).

Proof:

Write the number in a convenient way

Any positive integer that ends in 5 can be written as

$$N \;=\;10a+5 \qquad (a=0,1,2,\ldots)$$

The integer $a$ is exactly the tens-digit of $N$.

---

1. Why every square ends in 25

$$(10a+5)^2 \;=\;100a^{2}+100a+25 \;=\;100(a^{2}+a)+25$$

The first term is a multiple of 100, so it has no effect on the last two digits; what is left is 25.
Hence every even power of a number that ends in 5 ends in 25.

---

2. What happens for an odd power

Write an odd exponent as $2m+1\;(m\ge 1)$:

$$(10a+5)^{2m+1} \;=\;(10a+5)\,\bigl((10a+5)^2\bigr)^{m} \;\equiv\;(10a+5)\cdot25^{\,m}\pmod{100}.$$

Because $25^m\equiv25\pmod{100}$ for any $m\ge1$, we only need

$$25(10a+5)=250a+125.$$

Reduce this modulo 100:

$$250a+125 \;=\;100(2a)+{\color{#c00}{50a}}+{\color{#c00}25} \;\equiv\;50a+25\pmod{100}.$$

---

3. Parity of the tens digit decides the last two digits

• If $a$ is even (tens digit $0,2,4,6,8$):
  $50a\equiv0\pmod{100}$ ⇒ last two digits 25.

• If $a$ is odd (tens digit $1,3,5,7,9$):
  $50a\equiv50\pmod{100}$ ⇒ last two digits 75.

---

4. Putting it all together

For any integer $N$ ending in 5:

exponent $n$	last two digits of $N^n$
$n=1$	…05 (trivial)
even $n\ge2$	…25 (Section 1)
odd $n\ge3$ & tens digit of $N$ even	…25
odd $n\ge3$ & tens digit of $N$ odd	…75

---

Examples:
56745^134 = 25 (because last digit is 5 and even power)
56795^133 = 75 (last digit 5, second last digit odd, odd power)
5775^6 = 25 (even power means 25, second last digit doesn't matter)
5785^3 = 25

Powers of numbers ending in 24,76:
24^n = 76 if n is even 24 if odd
76^n = 76 for every n

Proof:

The “last-two-digits’’ game is really arithmetic mod 100

The last two digits of any integer are just that integer reduced modulo 100.
All we have to understand, then, is what happens to the residues

$$24 \pmod{100}\quad\text{and}\quad 76 \pmod{100}$$

when we raise them to powers.

---

Split the problem with the Chinese Remainder Theorem

Because $100 = 4 \times 25$ and $\gcd(4,25)=1$, every residue mod 100 is uniquely determined by its pair of residues mod 4 and mod 25.

number	mod 4	mod 25
24	$0$	$-1$
76	$0$	$+1$

So:

• Any integer ending in 24 is

  $$x\equiv 0\pmod 4,\qquad x\equiv -1\pmod{25}.$$

• Any integer ending in 76 is

  $$y\equiv 0\pmod 4,\qquad y\equiv +1\pmod{25}.$$

---

Raise them to a power

1. Behaviour mod 4

   Both 24 and 76 are multiples of 4, so for every positive integer $n$

   $$24^{\,n}\equiv 0\pmod4,\qquad 76^{\,n}\equiv 0\pmod4.$$

2. Behaviour mod 25

   Because $24\equiv-1\pmod{25}$:

   $$24^{\,n}\equiv(-1)^{n}= \begin{cases} -1 & n\text{ odd},\\ +1 & n\text{ even}. \end{cases}$$

   Because $76\equiv+1\pmod{25}$:

   $$76^{\,n}\equiv(+1)^{n}=+1\quad\text{for all }n\ge1.$$

---

Recombine the two congruences

Now solve the simultaneous congruences for a residue mod 100:

target pair	unique solution mod 100
$0\pmod4,\; -1\pmod{25}$	24
$0\pmod4,\; +1\pmod{25}$	76

Putting it all together:

• If $n$ is odd

  $$24^{\,n}\equiv 24\pmod{100};$$

  the last two digits are 24.

• If $n$ is even

  $$24^{\,n}\equiv 76\pmod{100};$$

  the last two digits are 76.

• For any $n\ge1$

  $$76^{\,n}\equiv 76\pmod{100};$$

  the last two digits are always 76.

---

A one-line summary

24 behaves like “–1 mod 25” but still ends in a multiple of 4; its powers therefore toggle between the two possible numbers that satisfy “multiple of 4 and ±1 mod 25”, namely 24 and 76.
76, already “+1 mod 25”, stays fixed forever.

Now we will use this property to compute last 2 digits for numbers ending in 2,4,8.
Note that:
2^10 = 1024
4^5 = 1024
8 = 2^3

So we will manipulate the numbers so that the last 2 digits become 24.
Examples:
Ex1: 5432^732 = 32^732 = 1024^366 = 34^366 = 76

Ex2:
84^76 = (4 * 21)^76 = 4^76 * 21^76
21^76 = (2)1 = 21
4^76 = (4^5)^15 * 4 = 24^15 * 4 = 24 * 4 = 96
21*96 = 16

Ex3:
Find the right most 2 digits of 7^405.
(7^4)^101 * 7
= (01)^101 * 7
= (0)1* 7 = 07

Ex4:
16^2000
= (4^2)^2000 = (4^5)^800 = 24^800 = 76

Ex5:
56^173
= 7^173 * (2^3)^173
= (01)^43 * 7 * 2^519
= 01 * 7 * (24)^51 * 2^9
= 1 * 7 * 24 * 12 = 7 * 88 = 16

Ex6:
44^94
= 11^94 * 4^94
 = (4)1 * 24^18 * 56
= 41 * 76 * 56
= 96

Highest power of a prime in any given factorial:
Let's compute power of each prime in 10!.
For 2:
2 occurs in every second number.
So 10/2 = 5
2^2 = 4 occurs in every fourth number.
So 10/4 = 2
2^3 = 8 occurs in every eighth number.
So 10/8 = 1
So total power of 2 in 10! = 8.

So keep dividing by powers of that prime until the greatest integer function starts returning 0.

Examples:
Ex1:
50! = 2^a * 3^b * 5^c * 7^d * 11^e * R
a + b + c + d + e = ?
a = 25 + 12 + 6 + 3 + 1 = 47
b = 16 + 5 + 1 = 22
c = 10 + 2 = 12
d = 7 + 1 = 8
e = 4
Answer = 93

Number of zeroes in given factorial:
Essentially we need to find pairs of 2 and 5.
But in any factorial, 5s will be less than 2s so it is enough to count 5s.

Examples:
Ex1:
50! = 2^47 * 5^12 ....
So number of zeroes = 12.

Ex2:
Number of zeroes in 139!
Just count power of 5 = 27 + 5 + 1 = 33

Ex3:
Find the highest power of 30 in 100!
30 = 2 * 3 * 5
So again just find power of 5.
20 + 4 = 24

Ex4:
Which greatest 2 digit integer has 5 factors.
Solution:
If a number = p1^a * p2^b * p3^c ...
Number of factors = (1+a)(1+b)(1+c)...
That number can be expressed as:
p1^4 => 5 factors.
2^4 = 16
3^4 = 81 = Largest such number

Ex5:
How many 2 digit numbers have 6 factors?
Solution:
Number can be p1^5 or p1^2.p2^1
Case 1: p1^5
2^5 = 32 Only one

Case 2:
p1 = 2(2^2 = 4), p2 = 3,5,7,11,13,17,19,23
p1 = 3(3^2 = 9), p2 = 2,5,7,11
p1 = 5(5^2 = 25), p2 = 2,3
p1 = 7(7^2 = 49), p2 = 2 

Total Case 2: 15
Total: 15+1 = 16