1
$\begingroup$

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

4 Answers 4

8

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

Are $15$ and $651$ coprime?

Are $16$ and $651$ coprime?

  • 0
    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.2012-06-08
5

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.

1

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

0

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.