Simple number theory questions (CRT)

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

• Two questions! 1: need $\gcd(a,n)=1$. 2: so that you can apply CRT. – Angina Seng Sep 12 '18 at 5:11
• 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. – Peter Sep 12 '18 at 11:48
• 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. – Vmimi Sep 13 '18 at 4:58
• "I have been watching the Chinese Remainder Theorem." Really? What channel is it on? – 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$$.