0
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Two questions! 1: need $\gcd(a,n)=1$. 2: so that you can apply CRT. $\endgroup$ Commented Sep 12, 2018 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
    Commented Sep 12, 2018 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
    Commented Sep 13, 2018 at 4:58
  • $\begingroup$ "I have been watching the Chinese Remainder Theorem." Really? What channel is it on? $\endgroup$ Commented Sep 28, 2018 at 3:52

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .