Find the modular inverse of a number when $b\neq1$

62 Views Asked by At

$ax \equiv b \mod N$

$1239x \equiv 5 \mod 154$

$7x \equiv 5 \mod 154$

$315x \equiv 5 \mod 154$

$x \equiv \frac{1}{63} \mod 154$

$63x + 154y = 1$

$\gcd(63,154) = 7 \neq1$ So there's not an inverse.

Is this the right method to, eventually, find the inverse when $b\neq1$?

2

There are 2 best solutions below

0
On BEST ANSWER

$$7x\equiv 5\mod{154}$$ has no solutions as you have correctly deduced. In general when we have that $$ax\equiv b\mod{ac},\qquad a\ne1$$ and $\gcd{(a,b)}=1$ then the equation has no solutions. This follows from the fact that we would have for any solution $x$ $$ax=b+kac$$ $$\implies b\equiv0\mod{a}$$ But if $\gcd{(a,b)}=1$ then $b\not\equiv0\text{ mod }a$ - a contradiction.

0
On

$$1239x \equiv 5 \pmod {154}\tag{1}$$ $$(154\cdot8+7)x\equiv 5 \pmod {154}$$ $$7x\equiv 5 \pmod {154} \tag{2}$$ The meaning of the last congruence is

$$157\mid 7x-5$$ or $$\exists k \in \mathbb{Z}:\; 7x-5=154k$$

From this we get $$7x-7\cdot 22\cdot k=5$$ and further $$7\mid5$$ which is a contradiction. So the equations $(2)$ and $(1)$ do not have a solution.

Similar reasoning shows that $$ax\equiv b \pmod c \tag{3}$$ has a solution if

$$ ax-ck=b\tag{4}$$ has a solution $(x,k) \in \mathbb{Z^2}$.

$(4)$ cannot have a solution if $\gcd(a,c) \not\mid b$, because this contradicts $(4)$.

If $\gcd(a,c) \mid b$ then $$\gcd\left(\frac a {\gcd(a,c)}, \frac c {\gcd(a,c)}\right) \not\mid \frac b {\gcd(a,c)} \tag{5}$$ and then we have a solution for

$$\frac a {\gcd(a,c)}x- \frac c {\gcd(a,c)}k= \frac b {\gcd(a,c)} \tag{6} $$ and therefore for $(4)$ and $(3)$.

The reason that $(6)$ has a solution if $(5)$ holds follows from the following theorem.

Theorem: If $a,b,c\in \mathbb{Z^+}$ and $\gcd(a,b)=1$ then $$ax\equiv b \pmod c \tag 7$$ has an integer solution $x$.

Proof: Because $\gcd(a,c)=1$ we can construct integers $u,v$ such that $$au+cv=1$$ by using the Extended Euclidean Algorithm. Therefore wwe have $$au \equiv 1 \pmod c \tag 8$$ Multiplying modular equation $(8)$ by $b$ gives $$a(ub) \equiv b \pmod c \tag 9$$ so $x=ub$ is a solution of $(7)$