# Let $a$ a positive integer such that $gdc(a,10) = 1$. Prove by induction: if $k>0, k \in \mathbb{Z}$ then $a^{4\cdot 10^k} \equiv 1 \pmod{10^{k+1}}$

Let $a$ be a positive integer such that $a$ is coprime with $10$.

Prove using induction that: for any positive integer k we have $a^{4\cdot 10^k} \equiv 1\pmod{10^{k+1}}$

I tried to use induction but I can't find any result. I need help.

$a^4 \equiv 1\pmod {10}$ from the Fermat - Euler theorem

Suppose $a^{4\cdot 10^k} \equiv 1\pmod {10^k}$ (heck this is true from the Fermat-Euler theorem, I guess we need a different proof of the base case.)

base case revisitied:

$(a^4 - 1) = (a+1)(a-1)(a^2 + 1)$

One of $(a+1),(a-1)$ is even.

If $5$ does not divide $(a+1),(a-1)$ then $a \equiv 2,3 \pmod 5$ in which case $5$ divides $a^2 +1$

$10$ divides $(a^4 - 1)$

$a^4 \equiv 1 \pmod {10}$

Inductive hypothesis:

Suppose $a^{4\cdot 10^k} \equiv 1\pmod {10^{k+1}}$

We must show that

$a^{4\cdot 10^{k+1}} \equiv 1\pmod {10^{k+2}}$

$a^{4\cdot 10^{k+1}} = (a^{4\cdot 10^{k}})^{10}$

$a^{4\cdot 10^{k}} = (n10^{k+1} + 1)$ from the inductive hypothesis

$(n10^{k+1} + 1)^{10} = \sum_\limits{i=0}^{10} {10 \choose i} n^i10^{i(k+1)}$

$10^{k+2}$ divides ten of the eleven terms of the above:

The remainder is 1.

• I didn't understand your method would you clarifate please – user431856 May 17 '17 at 18:15
• You will need to be more specific. This is a standard proof by induction. I show that it is true in the base case and show that when it is true for "n" it is also true for "n+1." That is if it is true when n=1. And, when it is true for n it is also true for n+1. Therefore it is true when n=2. and when it true when n=2 then it is true n=3 is true, etc. And so it is true for all natural numbers. – Doug M May 17 '17 at 18:25
• I just have a last question how can i prove that we can find a integer$N$ such that $N^3$ in decimal numeral system finish with the numbers $123456789$ using this question – user431856 May 17 '17 at 19:01
• Let $a^{4\cdot 10^8}\equiv 1\pmod {10^9}, a^{8\cdot 10^8}\equiv 1\pmod {10^9}, a^{8\cdot 10^8+1}\equiv a\pmod {10^9}, a^{8\cdot 10^8+1} = (a^{26666667})^3, N =123456789^{26666667}$ While there is a smaller N, we just need to prove that one exists, which we have done. – Doug M May 17 '17 at 20:46

Here is a much more simples proof without using induction.

If $gcd(a,10)=1$, then $gcd(a,10^{k+1})=1$. So, $$a^{\phi(10^{k+1})}\equiv1(mod 10^{k+1}),$$ but, $$\phi(10^{k+1})=\phi(2^{k+1}).\phi(5^{k+1})=2^k.5^k.4=4.10^k,$$ $$\Rightarrow a^{4.10^k}\equiv1(mod 10^{k+1})$$