Prove the gcd is 1 when a sequence is purely periodic 
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
 A: 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}$. 

A: 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.
A: See where your identity $10 x + m y = 1$ leads you when you take $m, 2 m, 3 m, ...$. What happens to $x$?
