Solution of $19 x \equiv 1 \pmod{35}$

Question

$19 x \equiv 1 \pmod{35}$

For this, may I know how to get the smallest value of $x$. I know that there is a theorem like $19^{34} = 1 \pmod {35}$. But I don't think it is the smallest.

Answer 1

Your question can be stated like this: What is the inverse of $19$ modulo $35$?

Since $\gcd(19,35) = 1$, $19$ is invertible mod $35$. Hence there is a unique solution $x\in\{0,\ldots,34\}$ of your equation. How to find it?

Method 1: You could just check all these possibilities to find it.

Method 2: A more structured (and in general, more efficient) way is to use the extended Euclidean algorithm on the pair $(35,19)$. It gives you numbers $a,b\in\mathbb{Z}$ with $19a + 35b = 1$. Now reading this equation modulo $35$, $$19a\equiv 1\mod 35.$$

Method 3: As you wrote, by Fermat $19^{34}\equiv 1\mod 35$, so $19\cdot 19^{33} \equiv 1\mod 35$. Now you can evaluate $19^{33}$ by the square-and-multiply algorithm. However note that in general, this is slower than the extended Euclid algorithm.

Concerning your question on the smallest $x$: The solution set has the structure $x_0 + 35\mathbb{Z}$. So if you have any solution $x_0$, the smallest solution is the remainder of $x_0$ modulo $35$.

Answer 2

Besides Euclides's Algorithm you can try other, sometimes quicker, methods. The following is done modulo $\,35\,$:

$$19\cdot2 =38=3\;,\;\;3\cdot 12=36=1\Longrightarrow1=3\cdot 12=19\cdot 2\cdot 12=19\cdot 24=1\Longrightarrow$$

$$\Longrightarrow 24=19^{-1}\Longrightarrow x=24$$

The "trick" above is to find some multiple of $\,19\,$ (namely, $\,3=19\cdot 2\,$) which is reasonably close to a multiple of $\,35\,$ (and thus its residue modulo $\,35\,$ is reasonable "small") and then work with that residue as it shall be easier to find its multiplicative inverse.

Answer 3

Hint $\rm\,\ mod\ 35\!:\,\ 19x\equiv 1\iff x\equiv \dfrac{1}{19}\equiv \dfrac{2}{38}\equiv \dfrac{2}3\equiv \dfrac{24}{36}\equiv\dfrac{24}1$

Remark $\ $ We used Gauss's algorithm for computing inverses $\rm\:mod\ p\:$ prime.

Beware $\ $ One can employ fractions $\rm\ x\equiv b/a\ $ in modular arithmetic (as above) only when the fractions have denominator $ $ coprime $ $ to the modulus $ $ (else the fraction may not uniquely exist, $ $ i.e. the equation $\rm\: ax\equiv b\,\ (mod\ m)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

Answer 4

Since, $\gcd(19,35)=1\implies \exists x_0,y_0\in \Bbb Z$ such that $19x_0+35y_0=1$.

You can apply euclid's algorithm, $$35=1\cdot19+16$$ $$19=1\cdot16+3$$ $$16=5\cdot3+1$$ $$\implies 1=16-5\cdot3=16-(19-1\cdot16)5=(35-19)-5(19-(35-19))=6\cdot35-11\cdot19$$ $$\implies19\cdot11=35\cdot6-1\implies 19\cdot(-11)\equiv 1\pmod {35}\implies 19\cdot24\equiv 1\pmod {35}$$

Answer 5

The problem is of the form $$ax\equiv\mod n.$$ If $\gcd(a,n)=1$, then the unique solution is given by $$x\equiv x_0\mod n$$ where $x_0$ is a particular solution of the given linear congruence. You may refer here. Note that $\gcd(19,35)=1.$ One such particular solution of $$19x\equiv 1\mod 35$$ is given $x_0=-11.$ Note that $-11\equiv 24\mod 35.$ The unique solution is given by$$x\equiv 24\mod 35.$$