# moduli problem with x inside a front variable

$(38x+23)/65 = 22 \mod 73$

I've tried to do $*65$ on both sides, so i have $(38x+23) = 43 \mod 73$ but i highly doubt that's even a valid operation.

I also tried to bruteforce it with no chance of success. what am I missing here.

wolfram-alpha states 62 as the solution to this. http://www.wolframalpha.com/input/?i=%2838x%2B23%29%2F65+%3D+22+mod+73

• Yes, you may multiply both sides of a congruence. If the number you multiply by is coprime to the modulus, then the resulting congruence will be logically equivalent to the original. Now that you've done that, how do you want to solve $38x+23=43$mod $73$? First step: identify how you would do it if it were an equality. Is there anything stopping you from doing that for this congruence? (Note: you can in fact "divide" within congruences; you multiply both sides by the multiplicative inverse of a number.)
– anon
Feb 19, 2013 at 18:24
• so both sides get multiplied with $38^{-1}$ leaving me with $x + 23 = 43 * 38^{-1} \mod 73$ if I am correct Feb 19, 2013 at 18:27
• You'll want to subtract the 23 from both sides before you multiply by $38^{-1}$.
– anon
Feb 19, 2013 at 18:29
• $x = 20 * 38^{-1} \mod 73$ this looks a lot more approachable than my shit up there Feb 19, 2013 at 18:32
• wheres that hint from math-gems gone just now? Feb 19, 2013 at 18:35

Yes, that's correct. Then $\rm\ mod\ 73\!:\, \ 38 x \equiv 20\:\Rightarrow\: x\equiv \dfrac{20}{38}\equiv \dfrac{40}{76}\equiv\dfrac{40}3\equiv\dfrac{-33}{3}\equiv -11$

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 is a special case of Gauss's algorithm for computing inverses $\rm\:mod\ p\:$ prime.

Hint: perhaps it helps to rid ourselves of the mod-bit;

$$\frac{38x + 23}{65} \equiv 22\pmod{73}$$

is equivalent to saying this:

$$\frac{38x + 23}{65} = 73n + 22, \quad n \in \mathbb{Z}$$

From thereon we may multiply both sides by $65$ and so forth (and we also observe that your operation is OK).

• okay so now I have an equation with two unknown variables. I do my basic stuff and end up with $x = ((73n/65)/38)- 1$ Feb 19, 2013 at 18:36
• I'm not sure about your equation (I get $x = \frac{4745n + 1407}{38}$), but the point is that all $x$ of that form, for the various $n \in \mathbb{Z}$, will be solutions to the original problem. That is to say, all such $x$ will be congruent to $22 \bmod{73}$. Feb 19, 2013 at 18:54
• Mishap on my part at the end there: I naturally mean that by plugging such $x$ into the original problem we'll get the congruence; the $x$'s themselves aren't congruent to $22 \bmod{73}$. Feb 19, 2013 at 19:03