Congruences
Take two integers and .
The notion of congruence is defined as:
where is considered to be greater than .
So, is congruent to iff divides .
A simple example: . is , and .
Let's look at a more interesting one:
.
Both numbers have in their units place, and because the result of their subtraction has in its units place, it is divisible by .
We can see that this is also true:
So, is congruent to iff both have the same remainder when divided by .
Applied to the first example, we have iff . It is true because is , and is also . Since they are equal to each other, .
There are some basic properties of congruences:
|
|
Reflexive Property |
|
Symmetric Property |
|
Transitive Property |
|
A number is congruent to its own remainder :
Why is that?
We can see that and the remainder of have the same remainder by taking the remainder of both sides:
Let's look at it with an example:
|
Let's say that is , and is . |
, so . |
Taking the remainder of both sides: . |
. |
And, finally, . |
One point to remember is that the remainder is between and : .
If , then .
And, why is that?
Since divides , it will also divide :
If , then .
And, why is that again?
Since divides , it will also divide :
Therefore,
That seems like ordinary arithmetic so far. But, let's take a look at an example:
If you want to cancel the 's, guess what? You can't:
Then, when can we cancel ?
The answer is when it has no common factors with . In other words, .
In order to cancel something, we have to have its inverse, a trivial example is , we can cancel the 's and get the result of .
Now, let's say that is an inverse of :
We can think of as an integer that acts like .
What we know is that if , that means we have a linear combination of and which is also : .
Since and are equal, they are congruent to each other :
is congruent to , so we can write it as such:
Then, what we're left with is this:
And, that means is an inverse of .
So, was indeed the inverse of all along, it is !
There is another way to cancel if it's relatively prime to :
If and , then we can multiply it by the inverse:
Reorganize it a bit:
Which means:
Therefore:
The point is that is cancellable iff has an inverse iff .
In other words, is cancellable iff is relatively prime to .