3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wrzlprmft Nov 19 '14 at 15:08
  • $\begingroup$ @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. $\endgroup$ – lhf Nov 19 '14 at 15:10
  • $\begingroup$ 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. $\endgroup$ – Wrzlprmft Nov 19 '14 at 15:17
  • $\begingroup$ @Wrzlprmft, I gave it another go. See my edited answer. $\endgroup$ – lhf Nov 19 '14 at 15:27
  • $\begingroup$ 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. $\endgroup$ – Wrzlprmft Nov 19 '14 at 15:42
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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