# When $a$ and $b$ are co-prime, is $F(x) = a x \mod b$, $x$ in $[0,b)$ , $a$ and $b$ co-prime, an injective function?

I'm trying to figure out whether my hardware function for mapping operating system pages to DDR memory controllers is injective:

$$F(x) = a x \pmod{b},\text{ where x in [0,b), a and b are co-prime}$$

My hunch is that it is injective and I think it has to do with the Chinese Remainder Theorem, though it may be some other theorem. Also, is "$a,b$ are co-prime" sufficient? Or does $a$ also need to be greater than $b$?

-

## 2 Answers

Yes, $\rm\ gcd(a,b)=1,\ \ b\:|\:ax\ \Rightarrow\ b\:|\:x\$ by Euclid's Lemma

Said functionally: $\rm\ ax\equiv 0\ \Rightarrow\ x\equiv 0\ \ (mod\ b)\$ so $\rm\ x\to ax\$ is injective.

More intuitively, by Bezout's identity, $\rm\ gcd(a,b)=1\ \Rightarrow\ a^{-1}\$ exists $\rm\ (mod\ b)\:.\:$ Therefore one can multiply $\rm \ ax\equiv ay\$ by $\rm\:a^{-1}\:$ to deduce $\rm\ x\equiv y\:$.

-

It is injective, your hunch is correct.

If $\displaystyle ax = ay \mod b$ then $\displaystyle a(x-y) = 0 \mod b$. Since $\displaystyle a$ and $\displaystyle b$ are co-prime, $\displaystyle x-y= 0 \mod b$ and hence $\displaystyle x = y$, as $\displaystyle x,y \in [0,b)$.

It does not matter whether $\displaystyle a \gt b$ or not.

-