Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

4 Answers 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.

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

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

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

Are $15$ and $651$ coprime?

Are $16$ and $651$ coprime?

share|improve this answer
    
The explicit factorization is not needed - see my answer. –  Bill Dubuque Jun 8 '12 at 22:48
5  
@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

Your Answer

 
discard

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.