How to find the inverse of a function when the modulo is involved

Question

What is the inverse of the following function?

$$ f(x) = 13x+74 \pmod{64} $$

Answer 1

Adding the assumption that $$f:[0,63)\cap\mathbb{Z}\rightarrow[0,63)\cap\mathbb{Z}$$

\begin{eqnarray} y&=&13x+74\pmod{64}\\ y&=&13x+10\pmod{64}\\ y+54&=&13x+64\pmod{64}\\ y+54&=&13x\pmod{64}\\ 5y+270&=&65x\pmod{64}\tag{$*$}\\ 5y+14&=&x\pmod{64} \end{eqnarray}

The key is seeing that $5$ is the inverse of $13$ in step $(*)$ since $5\times13=65=1\pmod{64}$.

So if $f(x)=13x+74\pmod{64}$ then

$$f^{-1}(x)=5x+14\pmod{64}$$

Verify this result as follows:

\begin{eqnarray} f^{-1}(13x+10)&=&5(13x+10)+14\pmod{64}\\ &=&65x+64\pmod{64}\\ &=&x\pmod{64} \end{eqnarray}

\begin{eqnarray} f(5x+14)&=&13(5x+14)+10\pmod{64}\\ &=&65x+192\pmod{64}\\ &=&x\pmod{64} \end{eqnarray}

Answer 2

First, 74= 10 (mod 64) so the equation is y= 13x+ 10 (mod 64). We can write that as y= 13x+ 10+ 64n and think of that as the "Diophantine equation" 13x+ 64n= y- 10.
1 13 divides into 64 4 times with remainder 12: 64- 13(4)= 12. 12 divides into 13 once with remainder 1: 13- 12= 1. Replacing that 12 with 64- 13(4) gives 13- (64- 13(4))= 4(13)- 1(64)= 1. Multiplying by y- 10, 13(4y- 40)+ 64(10- y)= y- 10. The solution is x= 4y- 40 (mod 64).

For the example, if the equation is 13x+ 10= 20 (mod 64), y= 20, so x= 4y- 10= 80- 10= 70= 6 (mod 64). Checking, 13x= 13(6)= 78= 78= 14 (mod 64) and them 13x+ 10= 14+ 10= 20 (mod 64).

Answer 3

A function like modulus is not invertible because it is not injective. If you consider $f(x) = 13x+74 \pmod{64}$ on the integer in the range $[0,63]$ then if $y\equiv 13x+74 \pmod{64}$ then $y\equiv 13x+10 \pmod{64}$. The modular inverse of $13 \pmod{64}$ is $5$ because $5\times 13 \equiv 1 \pmod{64}$ so we multiply both sides of the equation by $5$ getting $5y\equiv 65 x+ 50\to x\equiv 5y-50 \to x\equiv 5y+14$ which gives the inverse in the range of integers $x\in[0,63]$

Remark. if $x\in\mathbb{R}$ the problem is completely different

hope this helps

Answer 4

$\!\bmod 64\!:\,\ \overbrace{f\equiv 13x\!+\!10\iff x\equiv \color{#c00}{\dfrac{1}{13}}(f\!-\!10)}^{\large {\rm solve\,\ for\,\ } x}\equiv \overbrace{\color{#c00}5(f\!-\!10)\phantom{1^{1^{1^{1^1}}}}\!\!\!\!\!\!\!\!\!\!}^{\large 5\,f\ +\ 14},\ $ by $\,\ \overbrace{\color{#c00}{\dfrac{1}{13}}\equiv\dfrac{65}{13}}^{\ \ \large 1\,\ \equiv\,\ 65}\equiv\color{#c00}5$