What will be the remainder for the following division and what is the generale rule applied to it: $$ (-25)^{-1}\; mod\; 26 \;$$ ?
Asked
Active
Viewed 58 times
0
-
So you have to find a number $a= (-25)^{-1}$ which satisfies $a\times (-25)\equiv 1\pmod{26}$. With some calculation, you can see that $1\times (-25) \equiv 1\pmod{26}$, and so $(-25)^{-1} \equiv 1 \pmod{26}$. – peterwhy Jun 11 '17 at 20:39
2 Answers
1
In general, for the equation $$ax\equiv 1\pmod n,$$ this can be solved by running extended Euclidean algorithm on the pair $(a, n)$, which gives $x'$ and $y'$ that satisfy $$\begin{align*} ax' + ny' &= \gcd(a,n)\\ ((-25)\cdot1 +26\cdot 1 &= 1) \end{align*}$$
If $\gcd (a,n) = 1$, i.e. $a$ and $n$ are coprime, then the $x'$ will satisfy the equation.
Otherwise, if $\gcd(a,n)>1$, then the equation
$$ax + ny = 1$$
has no solution, because the left hand side is divisible by $\gcd (a,n)$ but the right hand side is not.
peterwhy
- 22,256
