# 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$?

• Note that a sequence $a_k$ has a period dividing $n$ precisely when $a_k=a_{k+n}$ – πr8 Jul 16 '16 at 12:25
• If you can use elementary group theory then it is easy because it follows from Lagrange's theorem. – lhf Jul 16 '16 at 12:44
• There are many ways to proceed depending on what you know. Do you know about the concept of "order" (additive and multiplicative)? Do you know any group theory? Do you know properties of gcd such as Bezout's identity or the gcd distributive law $\,\gcd(ca,cb) = c \gcd(a,b)?\$ – Bill Dubuque Jul 16 '16 at 14:47
• @BillDubuque this task is from Gelfand, and i wanted to solve it using things given in the book. In the book he only explained that if you have n things arranged in a circle, and you start from one and count every k-th thing, then eventually you will have a collision, and that means that two numbers have a common divisor, then he explains that if 2 numbers are relatively prime, then you will have all numbers repeating in your subsequence that are 0...n-1. This is all I was given. This book is for 9th grade students. – Pavel Jul 16 '16 at 15:28
• The definition is correct, but there appears to be little motivation. Note that you can do that exercise mechanically, i.e. the discriminant is a symmetric polynomial in the roots so you can use Gauss's algorithm to rewrite it as a polynomial in the elementary symmetric polynomials of the roots, which (Vieta) are the coefficients of the original polynomial. The algorithm is (conceptually) very simple, e.g. see the worked example in the prior link. – Bill Dubuque Jul 16 '16 at 17:27

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

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

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