Progressions modulo $n$

Question

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

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

Answer 2

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

Answer 3

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