2
$\begingroup$

Given an initial number $m$ and a modulo $n$, is there a way of determining some constant multiplier $k$ so that $(m \times k^x) \mod n$ will eventually yield all integers in $[1,n]$ by incrementing $x$?

Alternately, if I instead do $(m \times x) \mod n$ while incrementing $x$ every step, will that eventually yield every integer in $[1,n]$?

  • 0
    It seems that this is a multiplicative version of the famous theorem of arithmetic progressions by Dirichlet! I mean , if we replace * by +, and if k=n, then this geberates all primes! Moreover, if we conversely fix $k$ as a prime, then this implies the valuation on the rational field! Per chance this is a good starting point to introduce the notions of algebraic number theory! Thanks for the attention any way.2012-12-06

2 Answers 2

1

This happens if and only if $k$ is a primitive root modulo $n$, and $m$ is invertible.

There exists such a $k$ if and only if $n \in \{ 2,4, p^j , 2 p^j \}$, where $p$ is an odd prime.

Knowing a primitive root modulo $p$, there are simple ways to find $k$, but as far as I know, for large $p$ there is no way of finding a primitive root besides test and error.

To answer the new question $mx \pmod n$ will yield all the integers if and only if $m$ is invertible modulo $n$. That happens if and only if gcd$(m,n)=1$.

1

No it isn't. If $d:=\gcd(m,n) > 1$, this will not happen for any $k$. In this case, we namely have $d \mid mk^x$ for any $x$ and as $d$ is a divisor of $n$, also $d\mid mk^x - \alpha n$ for any $\alpha\in\mathbb Z$. So all numbers we get as $mk^x\pmod n$ are multiples of $d$.