Question

Let p be a prime. Consider the sequence 11,22,3, 44,55 modulo p. Prove that the resulting sequence is periodic with smallest period p(p - 1). (This means that p(p - 1) is the least among all positive integers l with the property that whenever n = m (mod l), we have n" = m" (mod p).)

Answer 1

We will first show that when l=p(p-1), then the property holds. Let
nmmod
, that is
n=m kl
for some integer k.

If
m 0 mod
, the trivially
Pn"- m m'
as .

Look at

m+kl n" - mmn -m m-mm (n" - m")(m' m m

.

(n" m")m" (m - 1)

n m n'
hence
Pn-m"
. Now since
m,p) = 1
$m^{kl} -1 \equiv 0 \mod p$ since .

Therefore .

Pn"- m m'

We now show that p(p-1) is the smallest integer with this property. Let l be any integer with the property.

Take $m= p \text{ and } n = p+l$ . Look at the following equation modulo p

$n^n -m^m \equiv (p+l)^{p+l} - p^p \equiv (p^p +l^p)(p+l)^l \equiv l^p (p+l)^l \equiv 0 \mod p$

Which means $p | l \text{ or } p | p+l$ . Hence .

Take $m=2 \text{ and } n=l+2$ , then

$n^n - m^m \equiv (l+2)^{l+2} - 2^2 \equiv (l^l+2^l)(l+2)^2-4 \equiv 2^l \times 4 -4$ as .

$\implies p|4(2^l-1)$. But p is an odd prime hence

. But 2 have order p-1 in the multiplicative group $\mathbb{F}^{\times}_p$ .

Hence .

We have that . The smallest such integer is p(p-1).

Therefore the period is p(p-1).