Discrete Math

posted by .

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 :)

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Discrete Math

    Can someone help? Very confused. . . John Sununus was once the governor of New Hampshire, and his name reminds one of the authors of a palindrome (a words which is spelt the same way forwards as backwards, such as SUNUNUS). How many
  2. math

    Which two is true as i'm confused A) 3+7 ß 10 mod 15 17 + 9 ß 4 mod 21 12 + 14 ß 0 mod 26 B) 4+11 ß 2 mod 13 9+7 ß 4 mod 12 13 + 13 ß 1 mod 25 C) 5+9 ß 4 mod 10 16 + 13 ß 3 mod 26 12 + 7 ß 6 mod 14 d)2+7 …
  3. Math

    Which Statements of congruence are true and which are false and why?
  4. math

    Which Statements of congruence are true and which are false and why?
  5. Math

    Which Statements of congruence are true and which are false and why?
  6. 7th grade health true or false

    11. Disagreements are a normal part of life. (1 point) True False 12. Talking to a trustworthy adult is the best way to stop sexual abuse and get help. (1 point) True False 13. Some conflicts are made worse by peer negotiation. (1 …
  7. Physical Ed

    11. Disagreements are a normal part of life. (1 point) True False 12. Talking to a trustworthy adult is the best way to stop sexual abuse and get help. (1 point) True False 13. Some conflicts are made worse by peer negotiation. (1 …
  8. math(Discrete)

    Determine whether the statement ∀x ∈ Z, ∃y, z ∈ Z[x = 5y + 7z] is true or false. Explain.
  9. DISCRETE MATH

    Let Z 5 be the relation of congruence modulo5. If 1 ≤ m, n ≤ 5,we define the product of two classes as [m][n] = [mn]. Explain why [3][4] = [2]. I know 3 x 4 = 12. 5 mod 12 = 2. but i don't know how to explain it. Help with …
  10. Discrete Math

    Let A = {x ∈ R| cos x ∈ Z}, B = {x ∈ R| sin x ∈ Z}. Is A ⊆ B?

More Similar Questions