How can an inverse of a modulo m be used to solve the congruence ax\equiv b(\bmod m) when gcd(a,m)=1.

permaneceerc 2021-05-12 Answered
How can an inverse of a modulo m be used to solve the congruence \(\displaystyle{a}{x}\equiv{b}{\left({b}\text{mod}{m}\right)}\) when gcd(a,m)=1.

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Plainmath recommends

  • Ask your own question for free.
  • Get a detailed answer even on the hardest topics.
  • Ask an expert for a step-by-step guidance to learn to do it yourself.
Ask Question

Expert Answer

mhalmantus
Answered 2021-05-14 Author has 8967 answers
Given information:
\(\displaystyle{a}{x}\equiv{b}{\left({b}\text{mod}{m}\right)}\)
Calculation:
In order to solve the congruence, we need an inverse of a modulo m.
Here, gcd (a, m) = 1 that means greatest common factor of a and m is 1. So, aand mare prime numbers then an inverse of a modulo m exists. Once we have an inverse \(\displaystyle\overline{{{a}}}\) of a modulo m, we can solve the congruence \(\displaystyle{a}{x}\equiv{b}{\left({b}\text{mod}{m}\right)}\) by multiplying both sides of the linear congruence by a.
Have a similar question?
Ask An Expert
13
 

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more
...