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.
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?
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
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.
2 ∈ 18 (mod 8)
It is true though, right?
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 ;.
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?
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)
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.
I think I found something about the overbar
_
a <--- equivalence class of a
_
b <---equivalence class of b
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)
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)
_
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 ≠ φ.
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!
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?
I would consider it false.
I am too guilty of double posting disregard above 11:51
We're even! lol
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?
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.
So, x = 1? Or can it be multiple answers? But what if I have a big equation like:
4x ≡ 320(mod n), n = 592
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, ...
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.
Great! Do make a good check to make sure it works.
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?
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.