# Reference for this theorem: $a, b$ coprime, $f(k) := ka \bmod b$, then $f$ is bijection on $\lbrace 0, …, b−1 \rbrace$.

I need to use the following theorem in a paper but have to expect that some of the audience (physicists) is not familiar with it, so I would like to reference it:

Let $a$ and $b$ be two coprime integers. Let $f(k) := ka \bmod b$. Then $$k≠j ⇒ f(k) ≠ f(j) \quad ∀ k,j ∈ \left\lbrace 0, …, b-1 \right\rbrace$$ or with other words: $f$ is a bijection on $\left\lbrace 0, …, b-1 \right\rbrace$.

What is the name of this theorem and if it does not have one, what is a sligthly more general theorem to reference instead? If even this does not exist, I am interested in a citable reference for this.

I have gone through Wikipedia’s lists of theorems and lemmas and checked everything named by less than two persons and did not find anything. I also checked a few books on number theory and did not find this statement.

Note that I am not looking for a proof (I can do that myself).

I don't think it has a name, but it follows from this fact:

If $X$ is finite then $f: X \to X$ is a bijection iff it is an injection iff it is a surjection.

You could also phrase the specific instance of that fact as follows:

Since $a$ is a unit mod $b$, the map $k \mapsto ka$ is a bijection.

If you want to get down to the details, you could say that $f$ is injective because

If $\gcd(a,b)=1$ and $b$ divides $ac$, then $b$ divides $c$.

This is an extension of Euclid's lemma and, like it, follows from Bézout's identity.

• My question is about the statement that $f$ is a injection in the first place. I wouldn’t have used the term bijection at all, weren’t it for the readability of the title. – Wrzlprmft Nov 19 '14 at 15:08
• @Wrzlprmft, $f$ is an injection because it is a surjection and that follows from the fact that $1$ is in the image, since $a$ is a unit. – lhf Nov 19 '14 at 15:10
• That’s all quite nice if you know about rings, unit, etc. But then you probably also know the statement in question anyway and I would not need to reference it. – Wrzlprmft Nov 19 '14 at 15:17
• @Wrzlprmft, I gave it another go. See my edited answer. – lhf Nov 19 '14 at 15:27
• I am afraid, there is still far too large a step from your extension of Euclid’s lemma to the statement in question, if you know next to nothing about number theory and similar. – Wrzlprmft Nov 19 '14 at 15:42

Proposition 2.1.13 from Elementary Number Theory: Primes, Congruences, and Secrets by William Stein (freely available on his site) is:

If $\text{gcd}(a,n) = 1$, then the equation $ax ≡ b ~(\text{mod } n)$ has a solution, and that solution is unique modulo $n$.

From there, it is only a small step to the required statement.