Post a New Question

Discrete Math

posted by on .

Congruence

True or False: (give reason)
_ __
2 ∈ 18 (mod 8)

Can someone please help with this problem? I'm confused. . . Thanks for any helpful replies.

  • Discrete Math - ,

    The definition of congruence is when
    (b-a)/m is an integer, then we can write
    a ≡ b (mod m).

    For example, we can write
    3 ≡ 15 (mod 4)
    because (15-3)/4 = 3 is an integer.
    Alternatively, 15/4 gives 3 as a remainder, but this latter case is not always true.

    Would this be sufficient for you to solve the given problem?

  • Discrete Math - ,

    So, this would read as :

    _ __
    2 = 18 (mod 8)

    Meaning this would be considered true, right?Because 18/8 = 2, and then 8 · 2 = 16, making the remainder 2.

    This might sound silly, but what does the symbol at the top of the number mean?
    _
    2

  • Discrete Math - ,

    Sorry, I do not know.

    I have seen the overbar used to mean:
    1. mean (average) value,
    2. recurring decimals,
    3. complement (of a set)
    4. complex conjugate
    but not in this case.

    You may want to check with your teacher. If it is in a computer generated exercise, there is usually a legend page into which you can look.

  • Discrete Math - ,

    2 ∈ 18 (mod 8)

    It is true though, right?

  • Discrete Math - ,

    2 ∈ 18 (mod 8)
    is not true, because ∈ is an operator for sets. For example:
    2∈ℝ is correct, because 2 is a member of the real numbers.

    Since 18 is not a set which includes 2, the above statement is not correct.

    However, if you meant
    2 ≡ 18 (mod 8)
    that would be correct.
    The code for ≡ is & # 8 8 0 1 ; without the spaces between & and ;.

  • Discrete Math - ,

    Hmmm...I kind of get what you are saying, but why is 18 not a set that does not include 2?

    Here is an example in the book that is true:
    _
    55 ∈ 7 (mod 3)

    _
    7 (the line goes over 7 in the above)

    Why would this be considered true?

  • Discrete Math - ,

    Could you tell me if I am correct in thinking:

    • With respect to congruence mod 29, 17 ∩ 423 = ∅ (True)

    • Let a, b, and n be integers with n > 1. Then a ≡ b (mod n) ⇔ a = b (False)

    •If ac ≡ bc(mod n), and gcd(c, n) = 1, then a ≡ b(mod m) (True)

  • Discrete Math - ,

    I'll get back to the last three proposition. But could you check in your book what the overbar stands for? It does not seem to be a typo at all.

  • Discrete Math - ,

    I think I found something about the overbar
    _
    a <--- equivalence class of a

    _
    b <---equivalence class of b

  • Discrete Math - ,

    Let a, b, and n be integers with n > 1. Then a ≡ b (mod n) ⇔ a = b (False)

    Correct.
    Note that:
    a=b => a≡b(mod n) but not the other way round.

    For the other part:
    ac≡bc (mod n)
    => (bc-ac)=kn k∈ℤ
    => (b-a)c=kn
    => (b-a)=k'n (GCD(c,n)=1)
    => b≡a (mod n)
    (true)

  • Discrete Math - ,

    OK. . .If you don't mind how about the these two too:

    • With respect to congruence mod 29, 17 ∩ 423 = ∅ (True)


    •If ac ≡ bc(mod n), and gcd(c, n) = 1, then a ≡ b(mod m) (True)

  • Discrete Math - ,

    _
    a <--- equivalence class of a

    is defined according to a given relation, which I presume in this case the (mod n).
    (See if you can find reference to the definition of the relation of the equivalence class).

    If that is the case, then
    __
    55 ∈ 7̄ (mod 3)
    means simply that
    55 ≡ 7 (mod 3)
    and so on.

    For:
    "With respect to congruence mod 29, 17 ∩ 423 = ∅ "

    Assuming the equivalence class is (mod 29).
    Then since 17 ≡ 423 mod 29 , we conclude that 17 ∩ 423 ≠ φ.

  • Discrete Math - ,

    If ac ≡ bc(mod n), and gcd(c, n) = 1, then a ≡ b(mod m) (True)

    is correct.

    I believe I mentioned it in the post of 10:54. Sorry that I made a double post. Fingers faster than the brain!

  • Discrete Math - ,

    Yea I was thinking that too, that it is the same thing,but I will double check with the teacher.

    So,With respect to congruence mod 29, 17 ∩ 423 = ∅ would be considered false, right?

  • Discrete Math - ,

    I would consider it false.

  • Discrete Math - ,

    I am too guilty of double posting disregard above 11:51

  • Discrete Math :) - ,

    We're even! lol

  • Discrete Math - ,

    Last thing I want to ask. . .

    5x ≡ 5(mod 25)

    Is there an easier way to derive to the answer. Because I believed I learned the long version.

    This is what I know:

    The possible values are 0, 1, 2, 3 . . .24

    5(0) - 5 = -5 not divisible by 25
    5(1) - 5 = 0 not divisible by 25
    5(2) - 5 = 5 not divisible by 25
    5(3) - 5 = 10 not divisible by 25

    So, I would this until I calculated a number that is divisible by 25, but there has to be an easier way, right? I think I saw something online where they found gcd. . .IDK though. If you're up to it can offer an easier way to decipher what x will equal?

  • Discrete Math - ,

    You were almost there!

    You can work backwards:
    5 mod 25 would typically be 5+25k | k∈ℤ.

    So the possible answers are 5, 30, 55, 70, etc. which gives 1,6,11,16..., in fact the answer would be x≡1 mod 5.

    Divide 5x≡mod25 by 5 to get x≡1 mod 5.

  • Discrete Math - ,

    So, x = 1? Or can it be multiple answers? But what if I have a big equation like:

    4x ≡ 320(mod n), n = 592

  • Discrete Math - ,

    Note that
    x≡1 mod 5
    means x could be 1, 6, 11, 16, ....

    Similarly
    4x≡320 (mod 592)
    would give
    x≡80 (mod 148)
    so
    x=80, 228, 376, 524, ...

  • Discrete Math - ,

    So, once I reduce it to this:x≡80 (mod 148). Then I have to do the trial and error process? Idk, I get how you got 80, but how did get 228, 376, 524. . .I think I see a pattern though each are incremented by 148. Hmm. . .I have another example that I would like to share, but I am going to work it out first, then post back in a few minutes to see if I am on the right track.

  • Discrete Math - ,

    Great! Do make a good check to make sure it works.

  • Discrete Math - ,

    So, I worked out a couple. . .

    1.) 4x ≡ 2(mod 6)
    x = 0, 4(0) - 2 = -2 is not divisible by 6
    x = 1, 4(1) - 2 = 2 is not divisible by 6
    x = 2, 4(2) - 2 = 6 is divisible by 6
    x = 3, 4(3) - 2 = 10 is not divisible by 6
    x = 4, 4(4) - 2 = 14 is not divisible by 6
    x = 5, 4(5) - 2 = 18 is divisible by 6
    x = {2, 5}

    2.) 4x ≡ 4(mod 6)
    x = 0, 4(0) - 4 = -4 is not divisible by 6
    x = 1, 4(1) - 4 = 0 is not divisible by 6
    x = 2, 4(2) - 4 = 2 is not divisible by 6
    x = 3, 4(3) - 4 = 8 is not divisible by 6
    x = 4, 4(4) - 4 = 12 is divisible by 6
    x = 5, 4(5) - 4= 16 is not divisible by 6
    x = {4}

    3.)5x ≡ 5(mod 5)
    x≣ 1 (mod 1)
    x = {1}

    Are these correct? If not, what am I doing wrong?

    7x ≡ 3(mod n), n = 11
    No x exist, right? But why?

    Also, back to the very first one:

    5x ≣ 5(mod 25)
    x ≣1 (mod 5)
    x = {1, 6, 11, 16, 21} <---Is this the whole answer?

  • Discrete Math - ,

    I will answer backwards.
    Let's go back to 5x≡5 (mod 25)
    You will notice that the remainder is always less than the divisor. So the question 5x ≡ 5 (mod 25) is valid.

    What it really means is that 5x has a remainder of 5 when divided by 25, and there are infinite possibilities, start with 5, add 25 to get 30, add 25 to get 55, etc to get, for example,
    5x=k: k∈{5,30,55,80,105,130...}
    =>
    x∈{1,6,11,16,21,26,....}
    So x≡1 (mod 5) is the answer, which is an infinite set of integers.

    Now for 7x≡3 (mod 11)
    Similarly, we look at the set
    7x≡ k: k∈{3,14,25,36,47,58,69,80,91,102...}
    I made a long list to demonstrate that integer solution for 7x returns in a period of 7, namely 14 and 91, 168, ...
    So yes, there are solutions for
    7x ≡ 3 (mod 11), namely
    x∈{14, 91, 168, 245, ...}

    For #3,
    3.)5x ≡ 5(mod 5)
    The question is not correct, because you cannot have 5 (mod 5) which could be translated to be 0 mod 5. in which case x=ℤ, i.e. all integers, since 5|5x ∀x∈ℤ.

    For the remaining one, it is much easier to work on the right hand side (like the last question 5x≡5(mod25)).
    For 4x≡4(mod 6)
    Look for numbers which satisfy 4 mod 6. Since 10 mod 6 = 4, therefore numbers such as 4, 10, 16, 22, 28....would satisfy the right hand side.
    Then you check the left-hand side to see if 4*1|4=1, so x=1 is in.
    4x=10 does not result in an integer solution, so 10 is out.
    4x=16 has an integer solution of x=4, so 16 is in, and so on.

    If you need further examples and explanations, post.

  • Discrete Math - ,

    OK you gave me a lot to think about. . .Thank you so much for your help. Until next time (which may be tomorrow). Thanks again :)

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question