Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
