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.

I'm trying to find which of $133x+203y=38$, $133x+203y=40$, $133x+203y=42$, and $133x+203y=44$ have integer solutions. I know that only the third equation suffices for these conditions because $gcd(133,203)=7$ which only divides $42$, but how do I find the solution with smallest possible $x\geq 0$ for $133x+203y=42$?

How do I find solutions $a,b$ to the equation $19a+29b=1$ by hand?

share|improve this question
4  
Since $\gcd(19,29) = 1$, you can use Euclid's algorithm to find $a$ and $b$ such that $19a + 29b = 1$. Then multiply solutions by $6$ to get $x$ and $y$ such that $19x + 29y = 6$ or $133x + 203y = 42$. –  TMM Apr 28 '13 at 23:30
    
Do you know Euclidean alogorithm? –  ᴊ ᴀ s ᴏ ɴ Apr 28 '13 at 23:30
    
@TMM Why $6$ Mr./Ms. TMM? –  Trancot Apr 28 '13 at 23:39
    
@Trancot: If $19a + 29b = 1$ then $19(6a) + 29(6b) = 6(19a + 29b) = 6$ so then $x = 6a$ and $y = 6b$ leads to a solution to $19x + 29y = 6$. –  TMM Apr 29 '13 at 11:39
add comment

1 Answer 1

up vote 2 down vote accepted

Correct. Note $\rm\ 19x\!+\!29y=6\, \Rightarrow\, mod\ 19\!:\ y \equiv \dfrac{6}{29}\equiv \dfrac{6}{10}\equiv \dfrac{12}{20}\equiv \dfrac{12}{1}\equiv -7\,\ $ so $\rm\,\ \color{#c00}{y = -7\!+\!19n},\:$ therefore $\rm\ x\, =\, \dfrac{6\!-\!29\,\color{#c00}y}{19} = \dfrac{6\!-\!29(\color{#c00}{-7+19n}))}{19}\, =\, 11\!-\!29n.$

Beware $\ $ One can employ fractions $\rm\ x\equiv b/a\ $ in modular arithmetic (as above) only when the fractions have denominator $ $ coprime $ $ to the modulus $ $ (else the fraction may not (uniquely) exist, $ $ i.e. the equation $\rm\: ax\equiv b\,\ (mod\ m)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

The above method is a special case of Gauss's algorithm for computing inverses. This always works for prime moduli, but may fail for composite moduli (in which case one may employ the extended Euclidean algorithm to compute inverses). Gauss's algorithm is often more efficient for manual calculations with small numbers.

share|improve this answer
    
Well put, thank you! –  Trancot Apr 29 '13 at 1:15
add comment

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.