Let n>1 and left f: N -> N be defined as follows, where a and b are integers.

f(x) = (ax + b) mod n

Then f has no fixed points if and only if gcd(a - 1, n) does not divide b.

How would I go about proving this? I tried by proving the contrapositive but I'm still stuck.


Let $a=4,b=6,n=10$. Then $f(x)=4x+6 \mod 10$. For $x=8$, we have $f(8)=4\times8+6 \mod 10=8$. Therefore $8$ is a fixed point.

Then by the statement given $\gcd(a-1,n)\not|b$.

But $\gcd(a-1,n)=\gcd(3,10)=1$ and $1|6$. $\therefore \gcd(a-1,n)|b$.

Thus the statement is not true.


Your Answer

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