(6)
Congruences
Description
Number theory contains an algebraic system of its own called the theory of congruences. The mathematical notion of congruences was introduced by Karl Friedrich Gauss in Disquisitiones (1801).
Definition
If and are two integers, and their difference is evenly divisible by , this can be written with the notation
This is expressed by the notation for a congruence
where the divisor is called the modulus of congruence. can equivalently be written as
where is an integer.
Note in the examples that for all cases in which , it is shown that . with this in mind, note that
Represents that is an even number.
Represents that is an odd number.
Examples
Properties of Congruences
All congruences (with fixed ) have the following properties in common
if and only if
If and then
implies that
Given there exists a unique such that
These properties represent an equivalence class, meaning that any integer
is congruent modulo to one specific integer in the finite field .
Congruences as Remainders
If the modulus of an integer , then for every integer
which can be understood to mean is the remainder of divided by , or as a congruence
Two numbers that are incongruent modulo must have different remainders. Therefore, it can be seen that any congruence holds if and only if and are integers which have the same remainder when divided by .
Example
is equivalent to
implies
is the remainder of divided by
The Algebra of Congruences
Suppose for this section we have two congruences, and . These congruences can be added or subtracted in the following manner
If these two congruences are multiplied together, the following congruence is obtained
or the special case where
Note: The above does not mean that there exists a division operation for congruences. The only possibility for simplifying the above is if and only if and are coprime. Mathematically, this is represented as
implies that if and only if
The set of equivalence classes defined above form a commutative ring, meaning the residue classes can be added, subtracted and multiplied, and that the operations are associative, commutative and have additive inverses.
Reducing Modulo m
Often, it is necessary to perform an operation on a congruence where , when what is desired is a new integer such that with the resultant being the least nonnegative residue modulo m of the congruence. Reducing a congruence modulo is based on the properties of congruences and is often required during exponentiation of a congruence.
Algorithm
Input: Integers and from with
Output: Integer such that
1. Let
2.
3.
4. Output
Example
Given
?
Note that is the least nonnegative residue modulo
Exponentiation
Assume you begin with . Upon multiplying this congruence by itself the result is . Generalizing this result and assuming is a positive integer
Example
This simplifies to
implies
implies
Repeated Squaring Method
Sometimes it is useful to know the least nonnegative residue modulo of a number which has been exponentiated as . In order to find this number, we may use the repeated squaring method which works as follows:
1. Begin with
2. Square and so that
3. Reduce modulo to obtain
4. Continue with steps 2 and 3 until is obtained.
Note that is the integer where would be just larger than the exponent desired
5. Add the successive exponents until you arrive at the desired exponent
6. Multiply all s associated with the s of the selected powers
7. Reduce the resulting for the desired result
Example
To find: 6149 mod 11 :
Adding exponents:
Multiplying least nonnegative residues associated with these exponents:
Therefore:
Inverse of a Congruence
Description
While finding the correct symmetric or asymmetric keys is required to encrypt a plaintext message, calculating the inverse of these keys is essential to successfully decrypt the resultant ciphertext. This can be seen in cryptosystems Ranging from a simple affine transformation
Where
To RSA public key encryption, where one of the deciphering (private) keys is
Definition
For the elements where , there exists such that . Thus, is said to be the inverse of , denoted where is the power of the integer for which .
Example
Find
This is equivalent to saying
First use the Euclidean algorithm to verify .
Next use the Extended Euclidean algorithm to discover the value of .
In this case, the value is .
Therefore,
It is easily verified that
Fermat s Little Theorem
Definition
Where is defined as prime, any integer will satisfy the following relation:
Example
When and
implies that
Conditions and Corollaries
An additional condition states that if is not divisible by , the following equation holds
Fermat s Little Theorem also has a corollary, which states that if is not divisible by and then
Euler s Generalization
If , then
Chinese Remainder Theorem
If one wants to solve a system of congruences with different moduli, it is possible to do so as follows:
A simultaneous solution exists if and only if with , and any two solutions are congruent to one another modulo .
The steps for finding the simultaneous solution using the Chinese Remainder theorem are as follows:
1. Compute
2. Compute for each of the different s
3. Find the inverse of for each using the Extended Euclidean algorithm
4. Multiply out for each
5. Sum all
6. Compute to obtain the least nonnegative residue
Example
Given:
Using the Extended Euclidean algorithm:
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|