Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – awllower Dec 6 '12 at 14:20
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.