Section 2 - Radford
Chapter 8: Congruences
Practice HW p. 62 # 1, 2, 3, 5, 6, Additional Web Exercises
In this section, we look at the fundamental concept of modular arithmetic, which is used in a variety of applications in number theory.
Modular Arithmetic
Definition: Given two integers [pic] and a positive integer [pic], we say that a is congruent to b modulo m, written
[pic]
if [pic]. The number m is called the modulus of the congruence.
Example 1: Explain why [pic] but [pic].
Solution: [pic] since [pic] or [pic] and [pic] or [pic]. However, [pic] since [pic] or [pic].
█
Theorem: [pic]if and only if [pic] for some integer k
Proof:
█
Fact: Computationally, [pic] gives the integer remainder of [pic]. We say that
[pic] if a and b produce the same integer remainder upon division by m.
For example, [pic] since both 23 and 8 produce are remainder of 3 when divided by 5, that is [pic] and [pic]. We can write [pic].
Note: When performing modular arithmetic computationally, the remainder r should never be negative (this fact comes from the division algorithm that when computing [pic] for [pic] that [pic]). Hence, when finding the remainder for [pic], look for the nearest integer that m divides that is less than b.
Example 2: Compare computing [pic] with [pic].
Solution:
█
Doing Modular Arithmetic For Larger Numbers With A Calculator
To do modular arithmetic with a calculator, we use the fact from the division algorithm that
[pic],
and solve for the remainder to obtain
[pic].
We put this result in division tableau format as follows:
[pic] (1)
Example 3: Compute [pic]
Solution:
█
Example 4: Compute [pic]
Solution: Using a calculator, we obtain [pic]. The largest integer less than 48.6 is 48. Hence, we assign q = floor(48.6) = 48. If we let b= 500234 and m = 10301 in (2), then
[pic].
The remainder of the division is r = 5786. Hence, [pic]. █
Example 5: Compute [pic]
Solution: Using a calculator, we obtain [pic]. The largest integer less than [pic] is [pic]. Hence, we assign q = floor(-28.7) = -29. If we let b= -3071 and m = 107 in (2), then
[pic]
Thus, [pic] █
Maple Commands for Doing Modular Arithmetic
Compute [pic]
> 1024 mod 37;
[pic]
Compute [pic]
> 500234 mod 10301;
[pic]
Compute [pic]
> -3071 mod 107;
[pic]
Generalization of Modular Arithmetic
Fact: The common remainder of two numbers have when they are divided can be used to define a congruence class. The remainder r will be the smallest positive integer in the congruence class. Suppose r is the remainder of [pic] divided by m, that is
[pic]
Theorem 1 says that then
[pic], where k is an integer.
Example 6: Find all elements of the congruence class [pic].
Solution:
█
Example 7 Find congruence class [pic] modulo 7.
Solution:
█
Note: For [pic], the set of distinct congruence classes are [pic], [pic], [pic], [pic], [pic], [pic], and [pic]. This partitions the integers Z into disjoint subsets.
Fact: Given [pic], Z can be partitioned into distinct congruence classes of the form
[pic]
Facts about Congruences
1. If [pic], then [pic] and [pic] for any integer t.
Proof:
█
2. If [pic] and [pic], then [pic], [pic] and [pic].
Proof:
█
Note: Computationally, in mod m arithmetic, we have
[pic]
[pic]
For example, we can by simplify [pic] as
Now, consider the problem of solving [pic]
Solving Equations Involving Congruences
We want to consider the problem of solving the linear congruence equation
[pic]
for x.
For example, consider the problem of solving the linear congruence
[pic]
Note that we can see that [pic] is a solution since
[pic]
Also, it can be seen that [pic] is a solution since
[pic]
However, [pic] and [pic] are in the same congruence class modulo 10, since both [pic] and [pic].
We want solution representations that are not in the same congruence class. These solutions are called incongruent solutions.
Fact: One way to find all of the incongruent solutions when solving a congruence for x in mod m arithmetic, set [pic] and find the values of x that satisfies the congruence. This is known as the method of brute force for finding the incongruent solutions.
Example 8: Find the incongruent solutions to [pic].
Solution:
█
However, the brute force method becomes less practical for finding incongruent solutions to congruences with larger moduli, like for example, solving the congruence
[pic]
The next theorem deals with this issue.
Theorem: Linear Congruence Theorem. Let a, c, and m be integers where [pic] and let [pic] For
[pic] *
i.) If [pic], then * has no solutions.
ii.) If [pic], then * has exactly g incongruent solutions. To find these g incongruent solutions , we first using the Euclidean Algorithm remainder solution process to find a solution [pic] to the equation
[pic]
Then a complete set of incongruent solutions is given by
[pic]
Proof: To prove part i, suppose there is a solution to [pic] when [pic]. Since [pic], then by the definition of congruence [pic], or [pic]or
[pic]
Since [pic], [pic] and [pic]. Hence [pic], which implies [pic]. This is a contradiction. Thus, when, [pic] , * has no solutions.
To prove part ii, assume [pic]. Since [pic], there exist integers [pic] and [pic] to the equation
[pic]
We multiply both sides of this equation by the integer [pic] (recall [pic]) to get
[pic]
Continued on Next Page
Hence,
[pic]
which says [pic] or by definition of congruence [pic]. Hence [pic] is a solution to *. To find the other [pic] incongruent solutions, suppose [pic]is another solution to *. Then
[pic]
or
[pic].
Then
[pic]
or
[pic] t is an integer
Since [pic], [pic] and [pic] and hence are integers. We divide both sides of the previous relationship by g.
[pic].
Hence, [pic] or [pic]. We claim [pic], for if not, there exists a common divisor [pic] where [pic] and [pic]. Thus [pic] and [pic] for integers u and v. Solving for m and a, we get [pic] and [pic]. Hence, [pic] and [pic], which contradicts that [pic] ([pic]).
Now, since [pic] and [pic], this implies that [pic].
Hence, we have
[pic]
or
[pic]
Now, that taking [pic] produces g incongruent solutions. Note, if [pic], a previous value would be repeated, since if [pic] for any [pic] would give
[pic]
Since [pic], this value will have been repeated. This completes the proof.
█
Example 9: Use the Linear Congruence Theorem to find all of the incongruent solutions to [pic]
Solution:
█
Example 10: Use the Linear Congruence Theorem to find all of the incongruent solutions to [pic]
Solution:
█
Example 11: Use the Linear Congruence Theorem to find all of the incongruent solutions to [pic]
Solution:
█
Corollary to the Linear Congruence Theorem: The congruence [pic] has a solution for x (note that [pic] is the multiplicative inverse of a modulo m if [pic]). The solution is unique for [pic].
Proof:
█
Solving Congruences of Higher Degree
Solving congruences of higher degrees are generally more difficult than linear congruences. If the modulus m is small enough, the brute force method will suffice.
Example 12: Find the incongruent solutions for [pic]
Solution:
█
Example 13: Find the incongruent solutions for [pic]
Solution:
█
However, the brute force method becomes more inefficient the larger the modulus. In our examples, we saw that [pic] has 4 solutions and that [pic] has none. Is there any way we can predict the number of incongruent solutions beforehand? The next theorem partially answers this question.
Theorem: Polynomial Roots Mod p Theorem. Let p be a prime and let
[pic]
be a polynomial of degree [pic] with integer coefficients and with [pic]. Then the congruence [pic]
[pic]
has at most d incongruent solutions.
Proof: Suppose there at least one polynomial where p does not divide the leading coefficient that has more distinct incongruent solutions then its degree. Let d be a polynomial of least degree for these polynomials given by
[pic]
Suppose [pic] be these incongruent solutions. For each incongruent solution [pic] of [pic], we know that
[pic]
Since [pic] is a zero, by the factor theorem for polynomials,
[pic]
where [pic] is of degree [pic], that is, [pic] has the form
[pic]
For the other incongruent solutions [pic] of [pic], we have
[pic]
Since [pic], it follows from the prime divisibility property that
[pic]. Hence, [pic] are incongruent solutions to [pic], which says that [pic] has d incongruent solutions, which is a contradiction that [pic] is the polynomial of least degree that has more incongruent solutions than its degree. Thus, the result holds.
█
Example 14: Find the incongruent solutions for [pic]
Solution:
█[pic][pic]
-----------------------
Take Floor of Quotient (largest integer lessﰋﰞﰟﰠﰡﰿﱀﱓﱔﱕﱖﱨﱩﱼﱽﱾﱿﲄﲅﲻﲼﳏﳐﳑﳒ﵁﵂︠︢짖짷뫷즨짷뫷즖賷짷緷쥫揷佞̝jᘀ㔀脈ࡕ洁H渄H甄Ĉᘉ침鄪㔀脈ᔏ渲ᘀ침鄪㔀脈̢ᱪǎᔀ㡨尲ᘀ渲䈀Ī䡅ࡕ瀁h̝౪ꏣĈ栖㋪n䩃ࡕ嘁Ĉ䩡ᘒ渲㘀脈⩂瀁h̢ﵪNjᔀ㡨尲ᘀ渲䈀Ī䡅ࡕ瀁h̢ljᔀ㡨尲ᘀ渲䈀Ī䡅ࡕ瀁h̝홪ꏟĈ栖㋪n䩃ࡕ嘁Ĉ䩡̘jᘀ渲䈀Īࡕ瀁h than calculator value of [pic]).
Remainder
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- gear freq using euclidean algorithm
- teaching cryptography in high school ti89
- cis 3362 homework 2 ucf computer science
- k means clustering example
- why a number theoretic calculator uccs
- radnor high school radnor township school district
- section 2 radford
- introduction computer action team
- section 1 rings and fields
Related searches
- chapter 8 section 2 photosynthesis
- chapter 8 section 2 photosynthesis answers
- article 2 section 2 of us constitution
- fmpm section 2 5
- 14th amendment section 2 simple
- 14th amendment section 2 explained
- 14th amendment section 2 meaning
- chapter 4 section 2 economics
- fmpm section 2 0
- article 2 section 2 of the constitution
- fmpm section 2 6
- section 2 2 physical properties