Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruences with fractions

  1. Nov 10, 2007 #1
    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

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

    For example:
    [itex]13 \equiv 4 (\mbox{mod } 9)[/itex] because [itex]1 \cdot 9 = 13-4[/itex]

    On the Wolfram mathworld website there are other examples in (8):
    [itex]2 \cdot 4 \equiv 1 (\mbox{mod } 7)[/itex]
    [itex]3 \cdot 3 \equiv 2 (\mbox{mod } 7)[/itex]
    [itex]6 \cdot 6 \equiv 1 (\mbox{mod } 7)[/itex]

    So far, so good.

    But then in (9) they write:

    [itex]\frac{1}{2} \equiv 4 (\mbox{mod } 7)[/itex]

    [itex]\frac{1}{4} \equiv 2 (\mbox{mod } 7)[/itex]

    [itex]\frac{2}{3} \equiv 3 (\mbox{mod } 7)[/itex]

    [itex]\frac{1}{6} \equiv 6 (\mbox{mod } 7)[/itex]

    which I don't understand.

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

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

    [itex]\frac{1}{2} - 4 = k \cdot 7:[/itex]

    [itex]\frac{1}{2} - 4 = k \cdot 7[/itex]
    [itex]\Rightarrow \frac{1}{2} - \frac{8}{2} = k \cdot 7[/itex]
    [itex]\Rightarrow -\frac{7}{2} = k \cdot 7[/itex]
    [itex]\Rightarrow k=-\frac{1}{2}[/itex]

    My questions:
    a) How are congruences defined for fractions? And why is (9) correct?
    b) Does (8) imply (9) ?
    Last edited: Nov 11, 2007
  2. jcsd
  3. Nov 10, 2007 #2
    Congruences are not defined for fractions.
  4. Nov 10, 2007 #3
    Instead of thinking about a/b as a fraction, let a/b mean a times the inverse of b.
    So when we write
    [itex]\frac{1}{2} \equiv 4 (\mbox{mod } 7)[/itex]
    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.
  5. Nov 11, 2007 #4
    Update: I added the link to the Wolfram mathworld website in my first post.

    And thanks for the answers so far.

    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?

    If I understood you correctly the following holds:

    [tex]ab \equiv c (\mbox{mod }m) \Longleftrightarrow \frac{c}{a} \equiv b (\mbox{mod } m)[/tex]

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

    [tex]3 \cdot 3 \equiv 2 (\mbox{mod }7) \Longleftrightarrow \frac{2}{3} \equiv 3 (\mbox{mod } 7)[/tex]

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

    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?


    Last edited: Nov 11, 2007
  6. Nov 11, 2007 #5
    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.
  7. Nov 11, 2007 #6
    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
    [itex]2a \equiv 1 (\mbox{mod } 7)[/itex] <=> 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 [itex]2a \equiv 1(\mbox{mod } 7)[/itex], then "a+7p" satisfies [itex]2(a+7p) \equiv 1 (\mbox{mod } 7)[/itex].

    [itex]2a \equiv 1 (\mbox{mod } 7)[/itex]
    <=> 2a-1 = 7k
    <=> 2a + 2*7p - 1 = 7k + 2*7p
    <=> 2(a+7p) - 1 = 7(k+2p)
    [itex]2(a+7p) \equiv 1 (\mbox{mod } 7)[/itex]
    Last edited: Nov 11, 2007
  8. Nov 11, 2007 #7
    What I mean is any number congruent to 0 mod 7 isn't going to have an inverse.
    This is important because here,
    [tex]ab \equiv c (\mbox{mod }m) \Longleftrightarrow \frac{c}{a} \equiv b (\mbox{mod } m)[/tex]
    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.
  9. Nov 11, 2007 #8
    Thanks for the answer MrJB!
  10. Nov 11, 2007 #9
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook