Prove the gcd is 1 when a sequence is purely periodic

Question

If the sequence $10^n\bmod m$ (where n>=0) is purely periodic, show that $\gcd(m,10) = 1$

I know that if the sequence is purely periodic, $a_i=a_{i+P}$ where P is the period. I can show using examples that the gcd(m,10) must be 1 but not generally

I know that if the gcd(m, 10) = 1

10x + my = 1

or

10x $\equiv$ 1 mod m

But from here I'm not sure how to prove the gcd must be 1

Answer 1

See where your identity $10 x + m y = 1$ leads you when you take $m, 2 m, 3 m, ...$. What happens to $x$?

Answer 2

Hint: Since the sequence is purely periodic, there exists a $p > 0$ such that $10^p \equiv 10 ^ 0 \equiv 1 \mod{m}$.

Can you conclude from here that $ \gcd(m,10) = 1 $?

---

If $ \gcd(m,10) = d \neq 1$, show that $10^p \neq 1 \pmod{m}$.

You should be able to show this directly.

If $ \gcd(m,10) = 1$, then there exists $p> 0$ such that $10^p \neq 1 \pmod{m}$.

There are multiple ways of showing this.

Approach 1: Apply Pigeonhole principle to the residues of $10, 10^2, 10^3 , \ldots 10^{m+1}$, to conclude that we have $ 10^a \equiv 10^b \pmod{m}$ with $a > b$.
Then, since $ \gcd(m,10) = 1$, we are allowed to divide by 10 repeatedly, to conclude that $10^{a - b} \equiv 1 \pmod{m}$.

$ $

Approach 2: Apply Bezout's lemma. See Fleablood's solution.

$ $

Approach 3: Apply Euler's theorem. $10 ^ {\phi(m)} \equiv 1 \pmod{m}$.

Answer 3

You are expected to know and use Bezout's Lemma.

Main part of Lemma: If $\gcd(a, m) = 1$ there then there will exist $x,y$ (integers) so that $ax + my = 1$.

Consequence: This means that if $\gcd(a,m) =1$ there will exist some integer $x$ so that $ax \equiv 1 \pmod m$.

Second but almost equally important part of Lemma: If $\gcd(a,m)=d\ne 1$ then there will exist $x,y$ so that $ax + my= d$ but also.... for any integer $w,v$ the number $aw+vw$ will be a multiple of $d$

Consequence: If $\gcd(a,m)\ne 1$ then finding an $x$ so that $ax \equiv 1 \pmod m$ is impossible. So there existing an $x$ so that $ax \equiv 1\pmod m$ is possible if and only if $\gcd(a,m) = 1$.

.......

Okay. What does this have to do with powers of $10$ and periodic sequences?

Well. For $w >0$ then $10^w = 10*(10^{w-1})$ and if $10^w\equiv 1\pmod m$ then $10*(10^{w-1})\equiv 1 \pmod m$ and that can only be possible if $\gcd(10, m) =1$.

Okay.... so what if it is never possible?

Well, $10^0 = 1$ and $1 \equiv \pmod m$.

Okay... but what if that is a one time event? After all $10^0=1$ and is NOT $10$ times anything so that is not a problem or a contradiction or anything that even needs to be addressed.

Okay, but suppose we were told that $a_n = 10^n\pmod m$ was purely periodic with a period of $P$ what would that mean?

Well that would mean that for any $k$ that $10^{k+P}\equiv 10^k \pmod m$.

Can we use that to show that $\gcd(10,m)=1$?

Well, if we can show that $10^w \equiv 1 \pmod m$ for some $w\ge 1$ that will prove $\gcd(10,m)=1$ but maybe $10^w$ never happens.

But $10^0\equiv 1\pmod m$.

Okay, but what if that was a one time event?

But $a_n = 10^n\pmod m$ was purely periodic with a period $P \ge 1$. So if $a_0 = 10^0=1\pmod m$, then $a_{0+P}=a_P = 10^{P}\equiv 1\pmod m$.

So there is a $w = P \ge 1$ so that $10^w \equiv 1\pmod m$....

And therefore $10^P = 1 + km$ for some integer $k$ .....

And therefore $10*10^{P-1} +(-k)m =1$ for some integers $10^{P-1}, -k$ and that is only possible, by Bezout's lemma, if $\gcd(10, m) =1$.

That's it. QED.