0
$\begingroup$

I understand that if $\gcd{(b,c)}=1$ then we can find $\frac{a}b\mod{c}$ by writing $$x\equiv \frac{a}b\mod{c}$$ $$bx\equiv a\mod{c}$$ then reducing $a$ and solving the modular equation by finding the multiplicative inverse of $b\mod{c}$. But when $\gcd{(b,c)}\ne1$, in particular if $b=c$ then how can one find a value for $$\frac{a}b\mod{c}$$ For example, the number $$\frac{146}7\equiv\frac{48}7\mod{7}$$ according to Wolfram: Alpha. How is this defined?

$\endgroup$
  • 1
    $\begingroup$ Well, $7x\equiv146\pmod7$ has no integer solutions.... $\endgroup$ – Lord Shark the Unknown Apr 7 at 17:09
  • 2
    $\begingroup$ You don't. $7\equiv 0$ and you can't divide by zero. Ever. $\endgroup$ – Oscar Lanzi Apr 7 at 17:09
  • $\begingroup$ $146 \equiv 48\pmod{7}$, so they probably just reduced the numerator. $\endgroup$ – Arturo Magidin Apr 7 at 17:30
  • $\begingroup$ It looks like they just repeatedly subtract $7$ from the value so that it falls within the range $0\lt x\lt7$ $\endgroup$ – Peter Foreman Apr 7 at 17:31
2
$\begingroup$

So in the case of $\dfrac{146}{7}$ mod 7, wolfram alpha reduced the numerator by multiplying the mod by the denominator to get 146 mod 49. The reason being for you able to do this is $\dfrac{146}{7}$ mod 7 can be written as $\dfrac{146}{7}$ $\pm$ $\dfrac{7x}{1}$ which then can be written as $\dfrac{146}{7}$ $\pm$ $\dfrac{49x}{7}$. From here on, you can just mod down the top number to get $\dfrac{48}{7}$ mod 7 as the smallest positive solution.

$\endgroup$
0
$\begingroup$

By abusing notation on can define the modulus $x \pmod n$ by looking for the real number $y$ in the range $[0,n)$ so that the difference $x-y$ is an integer multiple of $n$. In this case exactly this happens: $$\frac{146}{7}\pmod 7=\frac{140}{7}+\frac67\pmod 7=20+\frac67 \pmod 7=6+\frac67\pmod 7$$

For another example where the denominator is not the modulus, we see that

$$\frac{158}{7}\pmod{9}=\frac{154}{7}+\frac{4}{7}\pmod 9=22+\frac{4}{7}\pmod 9=4+\frac{4}{7}\pmod 9.$$

The real function that defines such operation (``$\pmod n$'') is thus $$f(x)=x-\left(\lfloor{\frac{x}n\rfloor}\cdot n\right)$$

$\endgroup$
  • $\begingroup$ I've revritten the answer. I hope it's fine as it stands. $\endgroup$ – b00n heT Apr 7 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.