Progressions modulo $n$ I don't understand how to do these 2 tasks:
1) Prove that any arithmetic progression modulo $n$ has a period that divides $n$.
2) Prove that any geometric progression modulo a prime number $p$ has a period that divides $p-1$.
A progression modulo some number $n$ is when you have a progression and then you replace every $a_i$ by $a_i\mod n$.
A period is the number of elements in the smallest repeated sub-sequence, for example $...1,2,3,1,2,3...$ has period $3$.
In the first task, if we have a progression with difference $d$, and $d$ and $n$ are relatively prime, then the period will be $n$ because $1$ is the greatest common divisor and that's why all elements ($0,...,n-1$) will be repeated but I don't understand how to prove for the general case. Maybe when the gcd is some other number $k$, it means that every $k-th$ number will be present in the repeated sub-sequence and the $n/period=k$?
 A: 1. Let $a_k$ be an arithmetic progression. Then 
$$ a_{k+m}=a_k+mr$$
Thus 
$$a_{k+m} \equiv a_k \pmod{n} \Leftrightarrow \\
mr \equiv 0 \pmod{n}  \Leftrightarrow \\
n|mr  \\
$$
Now prove that the smallest $m$ which satisfies this relation is 
$$m=\frac{n}{\gcd(n,r)}$$
which is a divisor of $n$.
2. Is similar:
Let $b_k$ be an arithmetic progression. Then 
$$ b_{k+m}=b_k\cdot r^k$$
If some $b_k \equiv 0 \pmod{p}$ the problem is easy, otherwise
Thus 
$$b_{k+m} \equiv b_k \pmod{p} \Leftrightarrow \\
r^m \equiv 1 \pmod{p}  \\
$$
Now, by Fermat Little Theorem you have $r^{p-1} \equiv 1 \pmod{p}$. If $m$ is your period, show that 
$$r^{\gcd(r,p-1)}\equiv 1 \pmod{p}$$
A: Hints: For (1), if the common difference is $d$, show that the period is $\dfrac{n}{\gcd(n,d)}$.  For (2), ignoring the trivial case where the common ratio is $0$ or when the sequence start with $0$, use the fact that there exists a primitive element $u$ modulo $p$ (i.e., there exists $u\not\equiv0\pmod{p}$ such that, for any $x\not\equiv0\pmod{p}$, $x\equiv u^l\pmod{p}$ for some nonnegative integer $l$). 
Alternative Hints:  Use the Pigeonhole Principle to establish that both sequences will eventually become periodic.  Assume that $\ell$ is the smallest period.  What happens if the division of $n$ in (1), or $p-1$ in (2), by $\ell$ leaves a remainder $r$ with $0<r<\ell$?  (In fact, it can be shown that, for (2), if $p$ is not necessarily prime, then $\ell$ must divide $\lambda(p)$, where $\lambda$ is the Carmichael function.)
A: 
Prove that any arithmetic progression modulo $n$ has a period that divides $n$.

Observe that $ |Z_n| = n $. Thus we have $ ng = 1 $, since $ \langle g \rangle \subseteq Z_n $, and from Larange's theorem, we know that $ |g| \bigm| n $, i.e. $ n = m|g| $ for some $ m $.
(to prove Larange's theorem, simply show that cosets partition the group and they have equal size)

Prove that any geometric progression modulo a prime number $p$ has a period that divides $p-1$.

Observe that $ g $ has an inverse in $ Z_n^\star $, iff. $ \gcd(g, n) = 1 $. Thus, we have $ |Z_p^\star| = p - 1 $, since primes are relatively prime to all $ n \neq p $.
