Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

share|improve this question
    
add comment

5 Answers

up vote 1 down vote accepted

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}$$

share|improve this answer
    
I don't think it is correct 19.11≡34(mod35) –  Jun Hao Mar 10 '13 at 11:00
    
@Avatar, Should it be $-11$?:) –  juniven Mar 10 '13 at 11:00
1  
@jun: Thanks for pointing out the error.I updated my answer. –  Aang Mar 10 '13 at 11:03
add comment

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$.

share|improve this answer
    
thanks for the explanation :) –  Jun Hao Mar 10 '13 at 11:11
add comment

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.

share|improve this answer
add comment

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).

share|improve this answer
add comment

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.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.