How to show these congruences?

Question

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

Answer 1

Hint: $651 = 3 \times 7 \times 31$.

Are $15$ and $651$ coprime?

Are $16$ and $651$ coprime?

Answer 2

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.

Answer 3

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

Answer 4

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.