I have been watching the Chinese Remainder Theorem, and have some questions about things related to it.

1) I have some questions about the inverse in modular arithmetic. I think that it's easy to prove by Bezout's identity, that if $gcd (a,n)=1$, then it's possible to find an interger $b$ such that $ab\equiv 1\pmod n$, but what if $a$ and $n$ aren't coprime? I think that it should be possible to find an inverse for $a$, but is there any rule that determines if it's possible or not?

How can you calculate the possible values of $b$ or the value of the inverse? I saw that it was possible to do it with the euclidean algorithm but have no idea how to do so.

2) My second question is about a problem related to the CRT.

"Show that there exists $99$ consecutive intergers $a_1,a_2, \ldots a_{99}$ such that each $a_i$ is divisible by the cube of some interger greater than $1$"

In the solution the establish the following system of congruences:

$$ x \equiv -1 \pmod {p_1^3}$$ $$ x \equiv -2 \pmod {p_2^3}$$ $$\vdots$$ $$ x \equiv -99 \pmod {p_{99}^3}$$

They had previously said that $p_1, p_2\ldots p_{99}$ were distinct prime numbers if so that system would have a solution, but what I can't really understand is why the primes are different, could you explain me?.

  • 2
    $\begingroup$ Two questions! 1: need $\gcd(a,n)=1$. 2: so that you can apply CRT. $\endgroup$ – Angina Seng Sep 12 '18 at 5:11
  • $\begingroup$ Consider the congruences $$a\equiv 1\mod 4$$ and $$a\equiv 4\mod 6$$ We cannot solve both congruences simultaneously because the first congruence implis that $a$ is odd and the second that $a$ is even. In general, we cannot guarantee a solution if the moduli are not pairwise coprime. Hence, the prime numbers must be pairwise distinct. $\endgroup$ – Peter Sep 12 '18 at 11:48
  • $\begingroup$ I know that but my question is why the primes are different, or if it´s possible that those primes are different? I think that I am not explaining really well what I want to say, but if you follow the same reasoning you can make that list of numbers as long as you want. $\endgroup$ – Vmimi Sep 13 '18 at 4:58
  • $\begingroup$ "I have been watching the Chinese Remainder Theorem." Really? What channel is it on? $\endgroup$ – Gerry Myerson Sep 28 '18 at 3:52

Suppose $a$ is invertible modulo $n$. Then, for some integer $b$, $ \ ab \equiv 1 \pmod n$. So, for some integer $u$, $\ abu = 1 + vn$. So $abu - vn = 1$, which implies $\gcd(a,n) = 1$.

You have already shown that $\gcd(a,n)=1$ implies that $a$ is invertible modulo $n$.

Hence, if $\gcd(a,n) > 1$, then $a$ is not invertible modulo $n$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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