3
$\begingroup$

I would like confirmation that my understanding of a congruence of two fractions is correct.

Suppose we have

$$\frac{2}{3} \equiv \frac{4}{6}\mod 5$$

What happened was multiplying both the numerator and denominator of the left fraction by $2$.

So $\frac{2}{3}$ is essentially the same as $3x\equiv 2 \mod 5$ and we can multiply both sides by $2$ since that is valid in modular arithmetic we get $6x \equiv 4\mod 5$ and rewriting that as a fraction we get $\frac{4}{6}$.

A fraction really represents that $x$ and since that $x$ remains unchanged via such manipulations then those fractions are essentially congruent.

Of course I am aware this is true only for valid fractions, i.e. where the denominator is invertible mod $5$.

Is my understanding of this correct?

$\endgroup$
4
$\begingroup$

Fractions work fine in modular arithmetic. They're not very commonly used, though.

If you want to use fractions, you have to stop thinking about $\frac23$ as $0.666\ldots$ and instead think of it as $4$ (at least in modulo $5$). Also, there is no simple way to just look at a modular fraction and know more or less what its value is, the way you can just know that $\frac{123456}{1000001}$ is very close to $0.123456$. In other words, small change in the denominator gives large changes in fraction value in modular arithmetic.

So there are a few mental roadblocks on the way to using fractions in modular arithmetic, and I suspect that that's why it isn't done more. That being said, if you do use fractions, the same rules that you learned in elementary school for regular (rational) fractions still all apply: How to expand / simplify fractions, how to add or multiply them, or how to check that they are equal. The technique known as "cross multiplication" still works: $\frac ab\equiv \frac cd\iff ad = bc$ (this does require that only invertible elements are allowed as denominators, though).

You can allow non-invertible elements as denominators, but then more care is needed. See, for instance, my answer here on allowing fractions with odd denominators (including $3$) in modulo $6$.

If you only allow invertible elements as denominators, then because they're already invertible, you're not really changing anything, as all fractions are elements that already exist as whole numbers. If you allow non-invertible elements, you basically get a smaller ring as a result (modulo $6$ with $3$ allowed as a denominator gives you what is essentially modulo $2$). Sadly, you can't get something "bigger" (the way $\Bbb Q$ is bigger than $\Bbb Z$), beause that requires you to have denominators which are neither invertible nor zero-divisors.

Edit: Since I apparently missed the real point of the question. Yes, those manipulations are fine. Whatever $\frac23$ is, give it the name $x$. By the definition of fractions, $3x = 2$. Multiplying both sides by $2$ can't make them not-equal, so $6x = 4$. Since $6$ is a valid denominator, by definition of fractions we get $x = \frac46$. What you have ultimately done is to expand the fraction $\frac23$ by $2$ and shown that this doesn't change the value of the fraction.

$\endgroup$
  • $\begingroup$ I see what you are saying, but it was not really the point of my question. I am wondering if my way of reaching the conclusion in the question is correct. $\endgroup$ – Michael Munta Mar 7 at 9:41
  • 1
    $\begingroup$ @MichaelMunta You're right. I added a bit at the end. $\endgroup$ – Arthur Mar 7 at 9:51
1
$\begingroup$

Yes. If $a,b,c,d$ are all co-prime to $n$ and $ad=bc \mod n$ then we know that $bd$ is co-prime to $n$ so it is invertible in $\mathbb{Z}_n$, and so we can divide by $bd$ to get

$\frac{a}{b}=\frac{c}{d} \mod n$

$\endgroup$
1
$\begingroup$

Yes, your understanding is correct, There are a few reasons that they typically aren't used though:

  • They aren't always defined ex. $\frac{5}{2} \bmod 6$
  • Because you can give a second name mod anything, you can get multiple answers when not coprime to the modulus ex. $\frac{3}{3}\equiv\frac{3}{-3}\bmod 6 $ at least in the sense of $3\equiv -3 \bmod 6$ but These give back two answers, The first is $1 \bmod 6$ if taken literally, the second is $-1\equiv 5 \bmod 6$, You can also get 3 mod 6, because $\frac{6x+3}{3}=2x+1$ which lands on all remainders corresponding to odd numbers mod 6.

So using them recklessly, comes with some perils.

$\endgroup$
-1
$\begingroup$

Yes, and just like you can do modular arithmetic to simplify ordinary arithmetic using integers, one can also do this for fractions. This looks impossible because of the multiple ways one can write a fraction modulo an integer representing a given number. But if it is known that the answer one is interested in, has a numerator between $0$ and $N$ and a denominator between $0$ and $D$ then a result modulo a number larger than $2 N D$ will allow one to reconstruct this rational number. As explained here, finding this fraction involves just the Euclidean algorithm.

$\endgroup$

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.