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.

Google Online Preview   Download