Digits Modulo 100

Think of the question like this: find $79^{79} \pmod{100}$ . We know $\gcd(79,100)=1$ . Also, $\phi(100)=100(1-\frac {1}{2})(1-\frac {1}{5})=40$ . Therefore, by Euler's Theorem, $79^{40} \equiv 1 \pmod{100}$ . Applying this to the problem, $79^{79}\times 79 \equiv (79^{40})^{2} \equiv 1$ . Let $\overline{ab}=79^{79}$ , where b may be zero. Note that we can assume a one- or two-digit number because in mod 100 every number can be written as a positive integer less than 100. We now have $79\times\overline{ab} \equiv 1 \pmod{100}$ . The tens digit of the LHS is 0 and the units digit is 1. Since the only digit that gives us a units digit of 1 when multiplied by 9 is 9 itself, we know that b=9. From there, we can test different different values of a starting with 0 and see which satisfies the equation. If you want to do it in a more orderly fashion, rewrite the equation as $(70+9)(10a+9) \equiv 100(7a+7)+10(9a+1)+1 \pmod{100}$ and you find that the tens digit is 0 when a=1. Either way, you find that a=1 and b=9. Therefore, $\overline{ab} \equiv 79^{79} \equiv 19 \pmod{100}$ . The last 2 digits are 19.

We wish to compute $79^{79} \pmod{100}$ We use the Binomial Theorem. $79^{79} = (80-1)^{79} = \sum_{i=0}^{79} 80^i\cdot(-1)^{79-i}$ . All of these terms are divisible by 100 except for the last two. The last two are $79\cdot 80 - 1 \equiv 19 \pmod{100}$ , so $79^{79} = 19 \pmod{100}$ .

Notice that, $79^{79}\equiv(-21)^{79} \pmod {100}$ . And consider the following: $\begin{aligned} (-21)^1&\equiv -21 &\pmod{100} \\ (-21)^2&\equiv 41 &\pmod{100} \\ (-21)^3&\equiv -61 &\pmod{100} \\ (-21)^4&\equiv 81 &\pmod{100} \\ (-21)^5&\equiv 1 &\pmod{100} \\ (-21)^6&\equiv21 &\pmod{100} \\ (-21)^7&\equiv -41& \pmod{100} \\ (-21)^8 &\equiv 61 &\pmod{100} \\ (-21)^9 &\equiv -81 &\pmod{100} \\ (-21)^{10}&\equiv 1 &\pmod{100} \\ \end{aligned}$

We see that $(-21)^n \pmod{100}$ has a period of 10. Thus, $79^79\equiv(-21)^79\equiv(-21)^9\equiv-81\equiv 19 \pmod{100}$ . So, the last two digits are 19.

[LaTeX edits - Calvin]

Computing the last 2 digits is equivalent to find $79^{79} \pmod{100}$ . We know that $100=2^2\cdot 5^2$ , so we can find the number $\pmod{4}$ and $\pmod{25}$ and we are done.

We know that $\phi{(4)}=2^2-2=2$ , so $79^{79}\equiv 3^{79}\equiv 3\cdot (3^{39})^2\equiv 3\equiv 19\pmod{4}$ . Also, $\phi{(25)}=5^2-5=20$ so $79^{79}\equiv 4^{79}\equiv (4^{-1})\cdot (4^{4})^{20}\equiv (4^{-1})\equiv 19 \pmod{25}$ , as know that $4\cdot 19=76\equiv 1\pmod{25}$ , thus $4^{-1}\equiv 19\pmod{25}$ Then, $79^{79}\equiv 19 \pmod{100}$ so $19$ is the answer.

To look for the last 2 digits of $79^{79}$ , it is the same as looking for the result modulo 100. By Euler's Theorem, $79^{40} \equiv 1 \pmod{100}$ , as $gcd(79, 100) = 1$ , and $\phi(100) = 40$ .

Thus $79^{80} \equiv 1 \pmod{100}$ , and $79^{79}$ modulo 100 is the inverse of 79 modulo 100. It's easy to see that $79 \times 81 \equiv -1 \pmod{100}$ . So $79^{79} \equiv -81 \pmod{100}$ , or $79^{79} \equiv 19 \pmod{100}$ .

First of all, we know that compute the last 2 digits of $79^{79}$ in the decimal representation is the same as calculating $79^{79}\pmod{100}$ , which is what we will do.

Is a well known fact that, for $N\in\mathbb{N^{*}}$ , $\phi(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k})$ where the $p_i$ are all the distinct prime factors of $N$ . So, since $100=2^{2}\cdot 5^{2}$ , we have $\phi(100)=100(1-\frac{1}{2})(1-\frac{1}{5})=40$ , and then, since $mdc(79,100)=1$ , using Euler's Theorem we have $79^{\phi(100)}\equiv 1\pmod{100}\iff 79^{40}\equiv 1\pmod{100}$ $\Longrightarrow 79^{80}\equiv 1^{2}\equiv 1\pmod{100}\Longrightarrow 79^{79}\cdot 79\equiv 1\pmod{100}$ $\Longrightarrow 79^{79}\equiv 79^{-1}\pmod{100}$ .

Then we need to calculate $79^{-1}\pmod{100}$ , which can be done by applying the Extended Euclidean Algorithm:
We have the following equalities
$100=79\times1+21\Rightarrow 21=100-79$ $79=21\times3+16\Rightarrow 16=79-21\times3$ $21=16\times1+5\Rightarrow 5=21-16\times1$ $16=5\times3+1\Rightarrow 1=16-5\times3$
So, starting from the last equality and then successively using the RHS of the last equality in the previous line, we have
$1=16-5\times3\\ =16-(21-16)\times3=16\times4-21\times3\\ =(79-21\times3)\times4-21\times3=79\times4-21\times15\\ =79\times4-(100-79)\times15=79\times19-100\times15$

Thus $79\times19-100\times15\equiv 1\pmod{100}\iff \\ 79\times19\equiv 1\pmod{100}\iff 79^{-1}\equiv 19\pmod{100}.$

Therefore, $79^{79}\equiv 79^{-1}\equiv 19\pmod{100}$ and the answer is 19 .

The last two digits of a number N is just N mod 100, so the problem is really asking for:

79^{79} \equiv x \pmod 100.

Euler's theorem states that a^{\phi(m)} \equiv 1 \pmod m if m and a are relatively prime. Since 79 and 100 are relatively prime, Euler's theorem is applicable.

/phi(N) is the number of numbers less than N that are relatively prime to N, which can also be expressed as N(1-1/p 1)(1-1/p 2)...(1-1/p i) where p 1,p 2,... p i are the distinct prime factors of N.

For the case N = 100, we find \phi(100) = 100(1-1/5)(1-1/2) = 100(4/5)(1/2) = 40.

So we know that 79^{40} \equiv 1 \pmod 100. Using the modulo rule for multiplication: 79^{40} \times 79^{39} \equiv x \pmod 100

79^{39} \equiv x \pmod 100.

Note that 79 = 80 - 1, so really we are solving: (80 - 1)^{39} \equiv x \pmod 100.

Begin to expand (80 - 1)^{39} to obtain

(-1)^{39}+39 80 (-1)^{38} + {39 \choose 2}(80^{2}(-1)^{37} + ....

But wait! Since 10 is a factor of 80, every term in the above expression that can be factored by 80^2 can also be factored by 10^2, which is 100!

This way, we can mod out all but the first two terms. So our new equation is

(-1)^{39} + 39 \times 80*(-1)^{38} \equiv x \pmod 100.

-1 + 3120 \equiv x \pmod 100. Mod out the 100's from 3120 to obtain

20 - 1 \equiv x \pmod 100.

19 \equiv x \pmod 100.

Therefore, the last two digits of 79^{79} = 19.

we get the last two digits of the ff: 79^1=79 79 79=41 41 79=39 39 79=81 81 79=99 99 79=21 21 79=59 59 79=61 61 79=19 19*79=01

and we will notice that the sequence will repeat after 10 multiplications. So we get 79th which is 19.

79=75+4 a number divided by 100 gives the numbers last 2 digits 79^79=((3 25)+4)^79 100=25 4
79^79=25 k+4^79 4^79=((4^5)^15) 4^4=(1024^15) 256=((1025-1)^15) (250+6) 4^79=(25 a)-6 79^79=(25 m)-6 therefore last 2 digits may be (25-6)or(50-6)or(75-6)or(100-6) 19 or 44 or 69 or 94 79^79=(80-1)^79=(4 20-1)^79=(4 n)-1 out of 19,44,69,94 the number of the form {(4*n)-1} is 19 therefore last 2 digits of 79^79=19

Computing for the last 2 digits of $79^{79}$ by finding its product several times, we have the following: $\begin{cases} {79^2= 41}\\{79^3=39}\\{79^4=81}\\...\\{79^9=19}\\{79^{10}=01}\\ \end{cases}$ Based from the cases, we found out that after multiplying $01$ by $79$ , the last two digits of $79^{11}$ is $79$ . Therefore, we are sure in this case that there are $10$ products per cycle. Thus, $79\pmod {10}\equiv 9\pmod {10}\equiv 9$ From the modulo operation above, it simply indicates of the last two digits of the $9^{th}$ product. Hence, the answer is $\boxed{19}$ .

to make last digit ending with 1 we have to select 79*79

79*79=-----41(last tow digit)

{( _ 41)raise to power39}*79

(40+1)raise to power 39=last to digit are 61 (by using binomial therom)

now 61*79=last digit are19(ans)

I have taken the concept of cyclicity in 2 digits rather than solving through mod theory ( congruences ). It means that i have followed the pattern of last 2 digits of consecutive powers of 79. The pattern which i get is as follows: 01,79,41,39,81,09,21,59,61,19,01.... Now by some logic we come to know that the last 2 digits of 79^70 are 01. And again skipping 9 powers means means skipping 9 last 2 digits which gives 19.

Solution 1: It is not hard to find high powers of $79$ modulo $100$ by repeated squaring. The following calculations can be easily done by hand using standard multiplication procedure, cut off at two digits.

$79^2 \equiv 41 \pmod {100}$ , $79^4\equiv 41^2 \equiv 81 \pmod{100},$ $79^8\equiv 81^2 \equiv 61 \pmod {100},$ $79^{16}\equiv 61^2 \equiv 21 \pmod {100},$ $79^{32}\equiv 21^2 \equiv 41\pmod {100},$ $79^{64}\equiv 41^2 \equiv 81 \pmod{100}.$

Because $79=64+15,$ $79^{79}\equiv 79^{64}\cdot 79^{15} \pmod {100}.$ To find $79^{15},$ we can first find $79^5=79^4\cdot 79\equiv 81 \cdot 79 \equiv 99 \equiv -1 \pmod{100}.$ Then $79^{15}\equiv (-1)^3\equiv -1 \pmod {100}$ and $79^{79}\equiv 81 \cdot (-1) \equiv 19 \pmod {100},$ so the answer is $19.$

For the following solutions let $\phi(N)$ be the number of integers less than $N$ that are coprime to $N$ (also known as Euler's Totient function). If $N = p_1^{q_1} p_2^{q_2} \ldots p_n^{q_n}$ then $\phi(N) = N\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\ldots \left(1 - \frac{1}{p_n}\right)$ .

Solution 2: Since $\phi(100) = 100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right) = 40$ , thus $79^{79} \equiv 79^{-1}\cdot 79^{40\cdot 2} \equiv 79^{-1} \pmod{100}$ by Euler’s Theorem. Since $\gcd(79,100) = 1$ , thus a multiplicative inverse exists. We can calculate the inverse using the Euclidean Algorithm and get that:

\begin{array}{1,1} 100 &=& 79\times 1 + 21 \\ 79 &=& 21\times 3 + 16 \\ 21 &=& 16\times 1 + 5 \\ 16 &=& 5\times 3 + 1 \end{array}

Thus, the above shows that $\gcd(79,100) = 1$ and we can calculate the inverse as follows:

\begin{array}{1,1} 1 & = & 16 - 5\times 3 \\ & = & 16 - (21-16\times 1)\times 3 \\ & = & 16\times 4 - 21\times 3 \\ & = & (79 - 21\times 3)\times 4 - 21\times 3 \\ & = & 79\times 4 - 21\times 15 \\ & = & 79\times 4 - (100-79)\times 15 \\ & = & 79\times 19 - 100\times 15 \end{array}

So we have, $1 \equiv 79\times 19 \pmod{100}$ $\Rightarrow 79^{-1} \pmod{100} = 19 \pmod{100}$ .

Solution 3: Since $\gcd(79, 100) = 1$ and $\phi(4)= 4\left(1-\frac{1}{2}\right) = 2$ , thus $79^{79} \equiv 3^1 \equiv 3 \pmod{4}$ . Since $\phi(25) = 25(1 - \frac{1}{5}) = 20$ , thus $79^{79} \equiv 4^{19} \equiv 4^{4\times4+3} \equiv 256^4 \times 64 \equiv 6^4 \times 14 \equiv 19 \pmod{25}$ . Since $19 \equiv 3 \pmod{4}$ , thus $79^{79} \equiv 19 \pmod{100}$ .

Use Euler's Totient Theorem with $n=200$ and $a=79$ (per the wiki), we get that $79^{80}\mod{200}\equiv79^{80}\mod{100}\equiv01$ . Upon realizing that $79\times19\mod{100}\equiv01$ , we are done.

• The Euler Theorem gives : $79^{40} \equiv 1 \pmod{100}$
• $79^{79}=79^{39+40}$ thus $79^{79} \equiv 79^{39} \pmod{100}$
• $79^{40} \equiv 1 \pmod{100}$ means that the 2 last digits of $79^{40}$ are $01$ and $79^{40}=79^{39}*79$
• The cycle of power of 9 gives a 9 for all odd powers so the 2 last digit must resolve this pattern : $A9*79=01$ which gives $9*A+71\equiv 0 \pmod{10}$ thus $A=1$ so the answer is $19$

We have $79^{\phi(100)}=79^{40}\equiv 1 \pmod{100}$ . Also, $19*79=(20-1)*(80-1)\equiv 1 \pmod{100}$ . Thus $79^{79}\equiv 19*79^{80}\equiv 19*(79^{40})^2\equiv \boxed{19} \pmod{100}$

By Euler's Theorem, (Totient Function of 100 is 40)

"79^40 is congruent to 1 (mod 100)"

Square both sides, you'll get: "79^80 is congruent to 1 (mod 100)"

---

I'm now looking for a number that is congruent to 1 mod(100) and also divisible by 79:

I tried 79*9=711, but it's not congruent to 1 (mod100)

I tried 79*19= 1501, It's now congruent to 1 (mod100)

---

Going back to "79^80 is congruent to 1 (mod 100)"

It can also be "79^80 is congruent to 1501 (mod 100)"

---

Dividing both sides by 79, It will now be "79^79 is congruent to 19 (mod 100).

Therefore, the last two digits of 79^79 is 19.

79^80=1(mod 100), 19*79=1(mod 100), 79^79=19(mod 100)

By Euler's Theorem, $79^{40}\equiv 1\pmod {100}$ , so $79^{80}\equiv 1\pmod {100}$ . One can find that the modular inverse of $79$ modulo $100$ is $19$ , so $79^{79}\equiv 79^{80}\cdot 19 \equiv \boxed{19}\pmod {100}$ .

$\begin{aligned} & 79^{79} \equiv \dfrac1{79} \equiv x \pmod{100} \\ \Rightarrow & 1 \equiv 79x \pmod{100} \\ \Rightarrow & 1 = 79x + 100y \\ \Rightarrow & x \equiv 19 \pmod{100} \end{aligned}$

The Extended Euclidean Algorithm is used to solve the linear diophantine equation for $x$ .

Hence, the answer is $\boxed{19}$

9^79 = ...89 -> so 1. one is 9 and we have carry 8; loop: 7 9 = ...3 - odd products; 3 9 = ...7 - even products; 79 is odd, so odd product and so 3+8(carry) = ...1 and so 19