Show that if $n ≥ 5$ then the last $2$ digits in the decimal expansion of $2^{n!}$ are $76$

Question

I know this can be solved by noticing that $2^{20}$ is congruent to $76 \mod 100$ and then performing an induction but I'm wondering if there is a way to tackle it without knowing that $76$ will be the last two digits, so for example using $2^{n!} ≡ x \mod 100$ and then splitting it into$\mod 4$ and$\mod 25$?

Answer 1

$76^n \equiv76 (mod 100)$

$76^1\equiv 76(mod100)$

for some natural number which $76^k\equiv 76(mod100)$,

$76^{k+1}=76\cdot 76^k \equiv 76\cdot 76=5776\equiv76(mod100)$

Answer 2

By Fermat's Little Theorem $2^{20}=1\mod 25$, and the only number less than 100 that is a multiple of 4 and equal to $1 \mod 25$ is 76. So

$2^{20}=76 \mod 100$

$76^2=76 \mod 100$

$\Rightarrow 2^{20k}=(2^{20})^k=76^k=76\mod 100$

for any positive integer $k$. And $20\mid n!$ for $n \ge 5$.

Answer 3

If understand your question correctly you are told by someone that there exist numbers $N$ and $x$ such that $2^{n!} \equiv x \mod 100$ for all $n \geq N$ but you are not told what $N$ and $x$ are and you want to see how far you can reduce the search space before doing any calculations?

Well as the previous answer states: you want your number $x$ to satisfy $x^k \equiv x \mod 100$ for every $x$, for which it is enough to show $x^2 \equiv x \mod 100$. Running with your idea of looking mod 4 and mod 25 we see that in each case the only solution to $x^2 \equiv x$ are $0$ and $1$. This leaves 4 possibilities:

$x \equiv 0 \mod 4$ and $x \equiv 0 \mod 25$ gives $x \equiv 0 \mod 100$

$x \equiv 0 \mod 4$ and $x \equiv 1 \mod 25$ gives $x \equiv 76 \mod 100$

$x \equiv 1 \mod 4$ and $x \equiv 0 \mod 25$ gives $x \equiv 25 \mod 100$

$x \equiv 1 \mod 4$ and $x \equiv 1 \mod 25$ gives $x \equiv 1 \mod 100$

Now the question is: running through $2^{1!}, 2^{2!}, \ldots$ which one will get hit first? We know that once we reach one of the solutions it will not let go and the others don't stand a chance anymore...

Of course we can rule out the two odd possibilities, leaving us with $0$ and $76$. Now for a number to be $0 \mod 100$ it must be divisible by $5$ which powers of $2$ are not, so 76 is the only remaining candidate. Hooray! We found the solution without calculating any power of 2.

However all we can say is this:

IF the person from the beginning is trustworthy and a solution does exist THEN this solution must be 76.

To be sure THAT a solution exists it seems we need to do some more work...