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

-

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.

-

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

-

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.

-

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

Are $15$ and $651$ coprime?

Are $16$ and $651$ coprime?

-
The explicit factorization is not needed - see my answer. –  Bill Dubuque Jun 8 '12 at 22:48
@Bill: indeed it is not, but it does make it easier to spot the issue here. –  Henry Jun 8 '12 at 22:49
But here one need only know if the modulus is divisible by $\:3\:$ or $\:5;\:$ or $\:2,\:$ resp. Computing a complete factorization is a big waste of time. This method would fail to be feasible for larger moduli, due to the difficulty of factorization. But the gcd method I used would still work quite quickly. –  Bill Dubuque Jun 8 '12 at 23:11