3
$\begingroup$

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 2

2

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

3

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.