Find all solutions for modulo equation

Question

Given $(133x \equiv 107) \pmod{91} , x \in N $

My first attempt was to do:

$133x - 91z \equiv 16 \pmod{91}$
$133x - (91z + 16) \equiv 0 \pmod{91}$
$133x - 16 \equiv 0 \pmod{91}$

From there on I do not know how to continue. Am I on the write way?

score 3 · Accepted Answer · edited Jun 10 '14 at 17:46

3

No such solution exists. This is because if we would have one such $x \in \Bbb Z$ such that $133x \equiv 107 \pmod {91}$, we would have a $k \in \Bbb Z$ such that $133x - 107=91k \iff 7(19x-13k)=107.$ This is not possible since $7 \nmid 107.$

edited Jun 10 '14 at 17:46

Gary Drocella

211

answered Jun 10 '14 at 17:39

Indrayudh Roy

2,256
13
22

That's a really good approach :) It may be worth another question, but how would I do this for $17x + 13y = 405$? – Peter Jun 10 '14 at 17:44
How do you find ${\rm gcd}(a,b)$, for any arbitrary $a,b \in \Bbb Z$? – Indrayudh Roy Jun 10 '14 at 17:46

score 0 · Answer 2 · answered Jun 10 '14 at 17:44

0

$ax\equiv b(\operatorname{mod} m)$ will have a solution iff gcd$(a,m)|b$

answered Jun 10 '14 at 17:44

usermath

3,516

score 0 · Answer 3 · answered Jun 10 '14 at 17:47

0

$A \equiv B \pmod C \implies \gcd(A,C)|B$

Therefore, $133x \equiv 107 \pmod {91} \implies \gcd(133x,91)|107 \implies 7|107$

Since $7$ does not divide $107$, no $x \in N$ exists such that $133x \equiv 107 \pmod {91}$

answered Jun 10 '14 at 17:47

barak manos

43,109

Find all solutions for modulo equation

3 Answers3