Congruences with Fractions: Understanding the Definition and Examples

[Edgardo]

I have a question about congruences involving fractions.

For integers a and b the following is defined:
a and b are congruent modulo m (m is a natural number) if there exists
an integer k such that k*m = a-b

a \equiv b (\mbox{mod } m) \Longleftrightarrow \exists k \in \mathbb{Z} : km = a-b

For example:
13 \equiv 4 (\mbox{mod } 9) because 1 \cdot 9 = 13-4On the Wolfram mathworld website there are other examples in (8):
2 \cdot 4 \equiv 1 (\mbox{mod } 7)
3 \cdot 3 \equiv 2 (\mbox{mod } 7)
6 \cdot 6 \equiv 1 (\mbox{mod } 7)

So far, so good.

But then in (9) they write:

\frac{1}{2} \equiv 4 (\mbox{mod } 7)

\frac{1}{4} \equiv 2 (\mbox{mod } 7)

\frac{2}{3} \equiv 3 (\mbox{mod } 7)

\frac{1}{6} \equiv 6 (\mbox{mod } 7)

which I don't understand.

At first I thought that for fractions a and b the definition is just extended:
a \equiv b (\mbox{mod } m) \Longleftrightarrow \exists k \in \mathbb{Z} : km = a-b
with a and b fractions (instead of just integers).

But the definition of congruence for fractions must be different since
there is no k \in \mathbb{N} such that

\frac{1}{2} - 4 = k \cdot 7:

\frac{1}{2} - 4 = k \cdot 7
\Rightarrow \frac{1}{2} - \frac{8}{2} = k \cdot 7
\Rightarrow -\frac{7}{2} = k \cdot 7
\Rightarrow k=-\frac{1}{2}My questions:
a) How are congruences defined for fractions? And why is (9) correct?
b) Does (8) imply (9) ?

 

[Kummer]

Congruences are not defined for fractions.

 

[MrJB]

Instead of thinking about a/b as a fraction, let a/b mean a times the inverse of b.
So when we write
\frac{1}{2} \equiv 4 (\mbox{mod } 7)
We don't mean the fraction 1/2, but 1 times the inverse of 2. The inverse of 2 is the number for which 2 * a = 1 mod 7, which is a = 4.
You can get (9) from (8) by multiplying each side of the congruence by the inverse of a certain element.
Also, be careful, 1/7 is not defined here mod 7 because 7 is congruent to 0 has no inverse. There is no number, a, for which 7 * a = 1 mod 7.

 

[Edgardo]

Update: I added the link to the Wolfram mathworld website in my first post.

And thanks for the answers so far.

Instead of thinking about a/b as a fraction, let a/b mean a times the inverse of b.
So when we write
\frac{1}{2} \equiv 4 (\mbox{mod } 7)
We don't mean the fraction 1/2, but 1 times the inverse of 2. The inverse of 2 is the number for which 2 * a = 1 mod 7, which is a = 4.

This is very helpful. I didn't know that the modular inverse was meant.
You wrote that "The inverse of 2 is the number for which 2 * a = 1 mod 7, which is a = 4".
Can I also choose a = 11 ?
Or does a have to be in a certain set?

You can get (9) from (8) by multiplying each side of the congruence by the inverse of a certain element.

If I understood you correctly the following holds:

ab \equiv c (\mbox{mod }m) \Longleftrightarrow \frac{c}{a} \equiv b (\mbox{mod } m)

For example: a=3, b=3, c=2 and m=7, then

3 \cdot 3 \equiv 2 (\mbox{mod }7) \Longleftrightarrow \frac{2}{3} \equiv 3 (\mbox{mod } 7)

Ok. I think I have worked out why this is so.

Also, be careful, 1/7 is not defined here mod 7 because 7 is congruent to 0 has no inverse. There is no number, a, for which 7 * a = 1 mod 7.

I understand that 1/7 is not defined in mod 7 because "There is no number a, for which 7 * a = 1 mod 7".
But what do you mean by the bold part?
And why the hint on 1/7?

Thanks.

Regards,
Edgardo

 

[Moo Of Doom]

You wrote that "The inverse of 2 is the number for which 2 * a = 1 mod 7, which is a = 4".
Can I also choose a = 11 ?
Or does a have to be in a certain set?

You can choose a = 11, but of course 11 = 4 mod 7. In fact, any number which satisfies this equation must be congruent to 4 mod 7. Therefore, we tend to choose the least positive integer that satisfies the equation, because all the other solutions can be gotten by adding multiples of seven to it.

 

[Edgardo]

Thanks for the answer Moo of Doom. Also for the hint that you get other possible values for "a" if you add multiples of 7. I was trying to find another value and found a=11 only after considering
2a \equiv 1 (\mbox{mod } 7) <=> 2a - 1 = 7k <=> 2a = 7k + 1
I plugged in k=1 which gives a=4,
then I set k=2 resulting in no possible a,
then I set k=3 and found a=11.

But as you said, it is easier to consider the following:
Let "a" satisfy 2a \equiv 1(\mbox{mod } 7), then "a+7p" satisfies 2(a+7p) \equiv 1 (\mbox{mod } 7).

Proof:
2a \equiv 1 (\mbox{mod } 7)
<=> 2a-1 = 7k
<=> 2a + 2*7p - 1 = 7k + 2*7p
<=> 2(a+7p) - 1 = 7(k+2p)
<=>
2(a+7p) \equiv 1 (\mbox{mod } 7)

 

[MrJB]

What I mean is any number congruent to 0 mod 7 isn't going to have an inverse.
This is important because here,
ab \equiv c (\mbox{mod }m) \Longleftrightarrow \frac{c}{a} \equiv b (\mbox{mod } m)
you are multiplying each side of the congruence by the inverse of a. If the inverse doesn't exist then this equation doesn't hold, or even make sense. The equation is true as long as a is not congruent to 0 mod 7.

 

[Edgardo]

Thanks for the answer MrJB!

 

[MrJB]

I think it's also worth noting that in other moduli there are numbers without inverses that are not congruent to 0 mod n. For example, 2 has no inverse mod 4.