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