How to show these congruences? Is there an element $x\in\mathbb Z$ such that $15x \equiv 1 \pmod{ 651}$ and is there a $y\in\mathbb Z$ such that $16y \equiv 1 \pmod {651}$?
 A: Hint: $651 = 3 \times 7 \times 31$.  
Are $15$ and $651$ coprime? 
Are $16$ and $651$ coprime?
A: Hint  $\rm\:\exists\, x\!:\, n\:\!x\equiv 1\pmod m\iff\exists\,x,y\!:\, n\:\!x+m\:\!y = 1\iff gcd(n,m) = 1,\:$ by Bezout.
$\rm But\ \, gcd(3\cdot 5,651) > 1\:$ since $\rm\:mod\ 3\!:\ 651\equiv 6+5+1\equiv 0,$
$\rm and\ \:gcd(\,2^{\,4},\,\ 651) = 1\ $ since $\rm\:mod\ 2\!:\ 651\equiv 1,\:$ i.e. $\:651\:$ is odd.
A: If there were an $x$ such that $15x \equiv 1 \pmod{651}$, this would imply that $15 \in (\Bbb{Z}/651\Bbb{Z})^\times$. However $\gcd(15,651)=3 >1$ and therefore it cannot be a unit in $\Bbb{Z}/651\Bbb{Z}$.
As for $16y \equiv 1 \pmod{651}$, since $\gcd(16,651)=1$, we have that it is a unit in $\Bbb{Z}/651\Bbb{Z}$. Therefore there exists a $y$ such that $16y \equiv 1 \pmod{651}$ namely $y = 529$.
A: For 1. we see that $GCD(15,651)=3$ so no solution will exist. For case 2. there is a solution since $GCD(16,651)=1$ and we can find a solution using Euclid's algorithm:
$$  651=40\times 16+11  $$
$$  16=11+5 $$
$$  11=2\times 5 +1  $$
So now working backwards we have
$$  1=11-2\times5=11-2\times(16-11)=3\times 11-2\times 16 =3 \times (651-40\times16)-2\times 16$$
$$ =3\times 651 -122 \times 16$$
Now taking this equation modulo $651$ we have
$$   -122 \times 16 \equiv 1 \pmod {651} $$
So $y=-122$ works or $y= 651-122=529$ if you'd prefer a positive integer.
