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

Congruence of Intergers and modular arthimetic

  1. Nov 21, 2009 #1
    Hey im just wondeirng if I have to prove a congruence,

    such as

    c^3 is congruent to d modulo 7,

    where d is set of {0,1 ,7}

    So in this problem to prove this example all I need to do is prove that it is a equivalence relation?

    So it is reflexsive, symmetric, and transitive?

    Is this correct?
     
  2. jcsd
  3. Nov 21, 2009 #2

    Mark44

    Staff: Mentor

    Assuming c is an integer, I believe that what you're trying to prove is that
    [tex]c^3 \equiv 0~mod~7[/tex]
    or
    [tex]c^3 \equiv 1~mod~7[/tex]

    If so, it's not true. 33 = 27 [itex]\equiv[/itex] 6 mod 7, and 53 = 125[itex]\equiv[/itex] 6 mod 7.
     
  4. Nov 21, 2009 #3
    Thanks mark. I just had a bit of another question if I could ask you ask well?

    It just how do i show

    b^3 +b^2 +1 does not divide by 5

    how do i prove it.

    Im thinking this way,
    cause i know that b^3 +b^2 +1 is not congruent to 0(mod5)

    therefore we use contradition to prove it. im just not sure how to use contradition? or maybe im looking at this in a completely bad light? maybe there is another method?
     
  5. Nov 21, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    If you meant "[itex]c^3[/itex] is congruent to one of 0, 1, 6 (mod 7)" then a perfectly valid way to do it is to look at all 7 possibilities: [itex]0^3= 0[/itex], [itex]1^3= 1[/itex], [itex]2^3= 8= 1[/itex], [itex]3^3= 27= 6[/itex], [itex]4^3= 64= 1[/itex], [itex]5^3= 125= 6[/itex], [itex]6^3= 216= 6[/itex], all "mod 7".
     
  6. Nov 21, 2009 #5

    Mark44

    Staff: Mentor

    If b^3 + b^2 + 1 is divisible by 5, the ones' digit in b^3 + b^2 + 1 has to be 0 or 5. Another way to say this is that b^3 + b^2 + 1 [itex]\equiv[/itex] 0 mod 5.

    Work with the integers modulo 5.
    If b [itex]\equiv[/itex] 0 mod 5, then b^3 [itex]\equiv[/itex] 0 mod 5, b^2 [itex]\equiv[/itex] 0 mod 5, so b^3 + b^2 + 1 [itex]\equiv[/itex] 1 mod 5. This means that the ones' digit has to be either 1 or 9.

    If b [itex]\equiv[/itex] 1 mod 5, then b^3 [itex]\equiv[/itex] 1 mod 5, b^2 [itex]\equiv[/itex] 1 mod 5, so b^3 + b^2 + 1 [itex]\equiv[/itex] 3 mod 5. This means that the ones' digit has to be either 3 or 8. Because b^3 + b^2 + 1 is always odd, you'll never get an 8 digit in the ones' place, so for this case, the ones' digit has to be 3.

    Continue this process for the other three equivalence classes to complete this proof.
     
  7. Nov 27, 2009 #6
    Hey mark, sorry for the late reply,

    Im just wondering what you mean by ones' digit
     
  8. Nov 27, 2009 #7

    Mark44

    Staff: Mentor

    In the decimal number system, each digit in the numeric representation indicates a power of 10. For example, 435 = 4 * 102 + 3 * 101 + 5 * 100. So 435 is 4 hundreds + 3 tens + 5 ones. The digit in the ones' place is 5 for this number.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Congruence of Intergers and modular arthimetic
  1. Modular Inverses? (Replies: 8)

  2. Modular arithmetic (Replies: 5)

  3. Modular Mathematics (Replies: 4)

  4. Modular arithmetic (Replies: 7)

Loading...