Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

Are $15$ and $651$ coprime?

Are $16$ and $651$ coprime?

share|cite|improve this answer
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

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.