Wednesday

October 26, 2016
Posted by **Francesca ** on Monday, March 14, 2011 at 3:17pm.

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**, Monday, March 14, 2011 at 7:03pmThe 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 -
**Francesca**, Monday, March 14, 2011 at 7:47pmSo, 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**, Monday, March 14, 2011 at 8:28pmSorry, 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**, Monday, March 14, 2011 at 9:06pm2 ∈ 18 (mod 8)

It is true though, right? - Discrete Math -
**MathMate**, Monday, March 14, 2011 at 9:12pm2 ∈ 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**, Monday, March 14, 2011 at 9:27pmHmmm...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**, Monday, March 14, 2011 at 9:32pmCould 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**, Monday, March 14, 2011 at 9:52pmI'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**, Monday, March 14, 2011 at 10:13pmI think I found something about the overbar

_

a <--- equivalence class of a

_

b <---equivalence class of b - Discrete Math -
**MathMate**, Monday, March 14, 2011 at 10:54pmLet 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 -
**Francesca**, Monday, March 14, 2011 at 11:18pmOK. . .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**, Monday, March 14, 2011 at 11:37pm_

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**, Monday, March 14, 2011 at 11:39pmIf 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**, Monday, March 14, 2011 at 11:42pmYea 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**, Monday, March 14, 2011 at 11:45pmI would consider it false.

- Discrete Math -
**Francesca**, Monday, March 14, 2011 at 11:55pmI am too guilty of double posting disregard above 11:51

- Discrete Math :) -
**MathMate**, Tuesday, March 15, 2011 at 12:02amWe're even! lol

- Discrete Math -
**Francesca**, Tuesday, March 15, 2011 at 12:11amLast 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**, Tuesday, March 15, 2011 at 12:32amYou 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**, Tuesday, March 15, 2011 at 2:52pmSo, 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**, Tuesday, March 15, 2011 at 5:12pmNote 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**, Tuesday, March 15, 2011 at 9:58pmSo, 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**, Tuesday, March 15, 2011 at 10:09pmGreat! Do make a good check to make sure it works.

- Discrete Math -
**Francesca**, Tuesday, March 15, 2011 at 10:27pmSo, 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**, Tuesday, March 15, 2011 at 10:57pmI 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 -
**Francesca**, Tuesday, March 15, 2011 at 11:12pmOK 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**, Tuesday, March 15, 2011 at 11:23pm:)