sequences and series - 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$?

Answer

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