0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I didn't understand your method would you clarifate please $\endgroup$ – user431856 May 17 '17 at 18:15
  • $\begingroup$ 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. $\endgroup$ – Doug M May 17 '17 at 18:25
  • $\begingroup$ 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 $\endgroup$ – user431856 May 17 '17 at 19:01
  • $\begingroup$ 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. $\endgroup$ – Doug M May 17 '17 at 20:46
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.