Posted by Francesca 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 
MathMate,
The definition of congruence is when
(ba)/m is an integer, then we can write
a ≡ b (mod m).
For example, we can write
3 ≡ 15 (mod 4)
because (153)/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 
Francesca,
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 
MathMate,
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 
Francesca,
2 ∈ 18 (mod 8)
It is true though, right? 
Discrete Math 
MathMate,
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 
Francesca,
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 
Francesca,
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 
MathMate,
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 
Francesca,
I think I found something about the overbar
_
a < equivalence class of a
_
b <equivalence class of b 
Discrete Math 
MathMate,
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)
=> (bcac)=kn k∈ℤ
=> (ba)c=kn
=> (ba)=k'n (GCD(c,n)=1)
=> b≡a (mod n)
(true) 
Discrete Math 
Francesca,
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 
MathMate,
_
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 
MathMate,
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 
Francesca,
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 
MathMate,
I would consider it false.

Discrete Math 
Francesca,
I am too guilty of double posting disregard above 11:51

Discrete Math :) 
MathMate,
We're even! lol

Discrete Math 
Francesca,
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 
MathMate,
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 
Francesca,
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 
MathMate,
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 
Francesca,
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 
MathMate,
Great! Do make a good check to make sure it works.

Discrete Math 
Francesca,
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 
MathMate,
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 55x ∀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 lefthand side to see if 4*14=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 
Francesca,
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 :)

Discrete Math :) 
MathMate,
:)