Congruence

Question

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

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

Answer 1

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?

Answer 2

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

Answer 3

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.

Answer 4

2 ∈ 18 (mod 8)

It is true though, right?

Answer 5

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 ;.

Answer 6

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?

Answer 7

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)

Answer 8

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.

Answer 9

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

_
b <---equivalence class of b

Answer 10

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)

Answer 11

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)

Answer 12

_
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 ≠ φ.

Answer 13

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!

Answer 14

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?

Answer 15

I would consider it false.

Answer 16

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

Answer 17

We're even! lol

Answer 18

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?

Answer 19

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.

Answer 20

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

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

Answer 21

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, ...

Answer 22

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.

Answer 23

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

Answer 24

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?

Answer 25

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∈&#8484.

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.

Answer 26

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