Q: do you learn this in college?

Yes, generally in a number theory class, although it can show up in some classes on discrete mathematics as well.

Q: Maybe someone can help me with a problem I'm working on. The 17 year cicadas are coming out in VA this year. Two years ago, the 13 year cicadas came out. From this we know that the solutions to 13a+2011=y and 17b+2013=y represent years when both will come out. Setting them equal, subtracting, etc, leaves us with 13a≡2(mod17) where a is the number of cycles of the 13 year cicadas until the two line up. Now here's my question: Is there a way other than brute force of solving a problem like this? I noticed this also comes up in RSA when finding a value for one's private key.

To solve an equation like: 13a≡2(mod17) we need to use modular inverses. The modular inverse of 13, which we will label as 13^-1, would be a number that we could multiply by 13 such that 13 * 13^-1 mod 17 = 1. We can find a modular inverse of 13 by brute force or by using the Extended Euclidian Algorithm. This program shows the extended euclidean algorithm. It shows that the modular inverse of 13 (mod 17) is 4. We can test it, 13 * 4 mod 17 = 52 mod 17 = 1 https://www.khanacademy.org/cs/modulo-inverse-using-the-extended-euclidean-algorithm/1604704343 Now that we have the modular inverse of 13 (mod 17) we can solve the equation. 13a≡2(mod 17) Now we multiply both sides by the modular inverse of 13 (mod 17) 13 * 13^-1 * a ≡ 2 * 13^-1 (mod 17) On the left we have 13 * 13^-1 mod 17 =1. On the right we replace 13^-1 by its value of 4. 1 * a ≡ 2 * 4 (mod 17) a ≡ 8 (mod 17) or a= 8+17 k where k is some integer Hope this makes sense

Q: 23 ( mod 5 ) does not equal 13!!

Anything mod 5 cannot equal 13. After all, 13 cannot be the remainder of anything/5

Q: I am stuck at this article of this subject. Could someone suggest that what could be learned first to have a better fundamental understanding of the subject? I think I need to break it down and learn it piece by piece.

A lot of this stuff is: -Set Theory -Relations A book I could suggest, which does a good job of covering this material is "Discrete Math with Applications" by Susanna Epp. You may find that this particular lesson is on the abstract side, and the material that comes further on is more practical. It may be worthwhile to try the material later on and come back to this material to see if it makes more sense after gaining some experience with the more practical side of things.

Q: Are you sure in the first paragraph, "Equivalent Statements", the line that claims "A = B + K * C (where K is some integer)" doesn't mean "A ≡ B + KC"? BECAUSE: A might not equal (B+KC) Because although they are in the same equivalence class, they might be two different integers. Im pretty crazy about being exact with my math, and nothing to blame, but I just wanted to know if it should be CONGRUENT rather than EQUIVALENT.

Certainly we can say that "A ≡ B + K * C" (mod C) , but we can make the even stronger statement that "A= B + K * C" is equivalent to the other statements. (This comes from the quotient remainder theorem). Note, not just any K will do. There is a unique K that exists for each A,B and C to make this true. Perhaps it may be helpful to think of it this way. "A ≡ B (mod C)" says that A and B are in the same equivalence class (mod C) "A=B+KC" can be interpreted as saying that any two values within the equivalence class are a multiple of C apart (this is true) Hope this makes sense

Question 1

can you explain more of reflexive properties with simpler examples? thanks.

Accepted Answer

*Reflexive property*

This is a property, that some *relations* have, that says that an element must be related to itself.

*An example relation with the reflexive property* :
We have a relation, R, that is "has the same father as" i.e. if x is related to y then x has the same father as y
we would write this as:
x R y

This relation has the reflexive property, since x must have the same father as x,  i.e. it is always true that x is related to x.
Written as:
x R x

*An example relation without the reflexive property* :
We have a relation, G, that is "is less than" i.e. if x is related to y then x < y
we would write this as:
x G y

This relation does not have the reflexive property, since x can not be less than x.

*Reflexive property for congruence modulo* :

Our relation, ≡ (mod C), is true when both elements have the same value mod C. i.e. if x ≡ y (mod C) then x mod C = y mod C

It is always true that x ≡ x (mod C) since x mod C = x mod C, thus the reflexive property holds for congruence modulo.
e.g.
5 ≡ 5 (mod 2)
7 ≡ 7 (mod 4)
13131313 ≡ 13131313 (mod 1554544774)

Hope this makes sense

Question 2

I think this section would be even more awesome if there would be an explanation of why it is so that C divides (A - B). So thats my question :-) How and why C divides (A - B) holds.

Accepted Answer

Here are some requested proofs:

*PROOF THAT THE EQUIVALENT STATEMENTS ARE EQUIVALENT*

By definition A≡B (mod C) means C | (A-B)
This is a definition, so no proof required.

*Proof that if C | (A-B) then A = B + K * C*

Suppose C|(A-B).
This means A-B = K * C where K is some integer
we rearrange this to obtain
A = B + K * C
Thus, if C | (A-B) then A = B + K * C
As was to be shown.

*Proof that if  A = B + K * C then A mod C = B mod C*

Definition of mod says:
if A = K * C + R where 0 <= R < C-1
then A mod C = R )

By the quotient remainder theorem:
A = Q * C + R where 0 <= R < C-1

By definition of mod: A mod C = R

Equating the two equations we have:
A = B + K * C = Q * C + R

We rearrange this to obtain
B = (Q-K) * C + R
By definition of mod: B mod C = R

A mod C = R = B mod C

Thus, if  A = B + K * C then A mod C = B mod C
As was to be shown

*Proof that if  A mod C = B mod C then C|A-B*

Since A mod C = B mod C we can write
(using the quotient remainder theorem):
A = P * C + R 
B = Q * C + R
where 0 <= R < C-1

A-B = (P * C + R) - (Q * C + R)
A-B = (P-Q) * C
clearly C | (P-Q) * C thus C | A-B
Thus if  A mod C = B mod C then C|A-B
As was to be shown

By combining these proofs you can start at any of the equivalance statements and obtain the others

*PROOF THAT CONGRUENCE MODULO IS AN EQUIVALENCE RELATION*

*Proof congruence modulo is reflexive*
We must show that A≡A (mod C)
The statement is equivalent to C|(A-A)
or C|0. 
0 = C * 0 thus C|0 is true
Thus congruence modulo is reflexive

*Proof congruence modulo is symmetric*
We must show that if A≡B (mod C) then B≡A (mod C)
The statement is equivalent to:
if C|(A-B) then C|(B-A)
Suppose C|(A-B) then (A-B) = C * K where K is an integer
Multiply both sides by -1
B-A = C * -K, thus C|(B-A)
Thus congruence modulo is symmetric

*Proof congruence modulo is transitive*
We must show that:
if A≡B (mod C) and B≡D(mod C) then A≡D(mod C)
The statement is equivalent to:
if C|(A-B) and C|(B-D) then C|(A-D)
A-B = C * K where K is an integer
B-D = C * M where M is an integer
add the two equations 
A-B + B-D = C * K + C * M
A-D = C * (K+M) thus C|(A-D)
Thus congruence modulo is transitive

We have shown that congruence modulo is reflexive, symmetric and transitive, thus congruence modulo, by definition, is an equivalence relation.

Hope this makes sense

Question 3

do you learn this in college?

Accepted Answer

Yes, generally in a number theory class, although it can show up in some classes on discrete mathematics as well.

Question 4

Maybe someone can help me with a problem I'm working on. The 17 year cicadas are coming out in VA this year. Two years ago, the 13 year cicadas came out. From this we know that the solutions to 13a+2011=y and 17b+2013=y represent years when both will come out. Setting them equal, subtracting, etc, leaves us with
13a≡2(mod17) where a is the number of cycles of the 13 year cicadas until the two line up. Now here's my question:
Is there a way other than brute force of solving a problem like this?
I noticed this also comes up in RSA when finding a value for one's private key.

Accepted Answer

To solve an equation like: 13a≡2(mod17) we need to use modular inverses. 
The modular inverse of 13, which we will label as 13^-1, would be a number that we could multiply by 13 such that 13 * 13^-1 mod 17 = 1.

We can find a modular inverse of 13 by brute force or by using the Extended Euclidian Algorithm.

This program shows the extended euclidean algorithm. It shows that the modular inverse of 13 (mod 17) is 4. We can test it, 13 * 4 mod 17 = 52 mod 17 = 1
https://www.khanacademy.org/cs/modulo-inverse-using-the-extended-euclidean-algorithm/1604704343

Now that we have the modular inverse of 13 (mod 17) we can solve the equation.
13a≡2(mod 17)
Now we multiply both sides by the modular inverse of 13 (mod 17)
13 * 13^-1 * a ≡ 2 * 13^-1 (mod 17)
On the left we have 13 * 13^-1 mod 17 =1. On the right we replace 13^-1 by its value of 4. 
1 * a ≡ 2 * 4 (mod 17)
a ≡ 8 (mod 17)
or
a= 8+17 k where k is some integer

Hope this makes sense

Question 5

23 ( mod 5 ) does not equal 13!!

Accepted Answer

Anything mod 5 cannot equal 13. After all, 13 cannot be the remainder of anything/5

Question 6

I am stuck at this article of this subject. Could someone suggest that what could be learned first to have  a better fundamental understanding of the subject? I think I need to break it down and learn it piece by piece.

Accepted Answer

A lot of this stuff is:
-Set Theory
-Relations

A book I could suggest, which does a good job of covering this material is "Discrete Math with Applications" by Susanna Epp.

You may find that this particular lesson is on the abstract side, and the material that comes further on is more practical. It may be worthwhile to try the material later on and come back to this material to see if it makes more sense after gaining some experience with the more practical side of things.

Question 7

Are you sure in the first paragraph, "Equivalent Statements", the line that claims "A = B + K * C (where K is some integer)" doesn't mean "A ≡ B + KC"? BECAUSE: A might not equal (B+KC) Because although they are in the same equivalence class, they might be two different integers. Im pretty crazy about being exact with my math, and nothing to blame, but I just wanted to know if it should be CONGRUENT rather than EQUIVALENT.

Accepted Answer

Certainly we can say that  "A ≡ B + K * C"  (mod C) , but we can make the even stronger statement that "A= B + K * C" is equivalent to the other statements. 
(This comes from the quotient remainder theorem). 
Note, not just any K will do. There is a unique K that exists for each A,B and C to make this true.

Perhaps it may be helpful to think of it this way.
"A ≡ B (mod C)" says that A and B are in the same equivalence class (mod C)
"A=B+KC" can be interpreted as saying that any two values within the equivalence class are a multiple of C apart (this is true)

Hope this makes sense

Computer science theory

Course: Computer science theory > Unit 2

Equivalence relations

Equivalent Statements

Congruence Modulo is an Equivalence Relation

Why do we care that congruence modulo C is an equivalence relation ?

Example

Want to join the conversation?