0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$
    – anon
    Feb 19, 2013 at 18:24
  • $\begingroup$ so both sides get multiplied with $38^{-1}$ leaving me with $x + 23 = 43 * 38^{-1} \mod 73$ if I am correct $\endgroup$
    – blacksmth
    Feb 19, 2013 at 18:27
  • $\begingroup$ You'll want to subtract the 23 from both sides before you multiply by $38^{-1}$. $\endgroup$
    – anon
    Feb 19, 2013 at 18:29
  • $\begingroup$ $x = 20 * 38^{-1} \mod 73$ this looks a lot more approachable than my shit up there $\endgroup$
    – blacksmth
    Feb 19, 2013 at 18:32
  • $\begingroup$ wheres that hint from math-gems gone just now? $\endgroup$
    – blacksmth
    Feb 19, 2013 at 18:35

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$ $\endgroup$
    – blacksmth
    Feb 19, 2013 at 18:36
  • $\begingroup$ 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}$. $\endgroup$
    – Jakob Streipel
    Feb 19, 2013 at 18:54
  • $\begingroup$ 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}$. $\endgroup$
    – Jakob Streipel
    Feb 19, 2013 at 19:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .