2

Given a prime p1 and a prime p2 (where p2 < p1), I made the observation that with a number n (where n increases by 1 from the value 1) the equation below results in two properties:

x = (p2 * n) mod p1
  • The first repeat is the value p2 where n = p1 + 1.
  • Somewhat as a function of the first property all the values in the range 0..p1 are consumed before reaching that repeat.

I've tested this property on paper with small primes and with some large primes by writing some code to confirm these properties, but does anyone know why this property holds?

Sean Parsons
  • 123

1 Answers1

3

It's because when $a$ and $b$ have no common prime factor, then there are integers $x$ and $y$ with $x\cdot a + y \cdot b = 1$. In your case, $p_1$ is prime, and $1 < p_2 < p_1$ (we don't even need that $p_2$ is prime), so $p_1$ and $p_2$ have no common prime factor, hence there is an $x \in \mathbb{N}$ with $x\cdot p_2 \equiv 1 \pmod{p_1}$.

Then you can solve the congruence

$$n\cdot p_2 \equiv k \pmod{p_1}$$

by setting $n \equiv x\cdot k \pmod{p_1}$, hence the remainders of $n\cdot p_2$ modulo $p_1$ for $1 \leqslant n < p_1$ cover all nonzero remainders ($n = p_1$ covers $0$).

Another way to see it is that if $n\cdot p_2 \equiv m\cdot p_2 \pmod{p_1}$, we have $(n-m)\cdot p_2 \equiv 0 \pmod{p_1}$, so $p_1$ must divide $n-m$ (since it doesn't divide $p_2$), and thus all remainders $n\cdot p_2$ modulo $p_1$ for $0 \leqslant n < p_1$ are different. Since there are only $p_1$ remainders, the $p_1$ different ones must cover all.

Daniel Fischer
  • 206,697