WWW.BOOK.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Books, dissertations, abstract
 
<< HOME
CONTACTS



Pages:   || 2 |

«2.5 Congruences For this section, we think of m as a fixed positive integer. Definition 15. We say that a is congruent to b modulo m, and we write ...»

-- [ Page 1 ] --

2.5 Congruences

For this section, we think of m as a fixed positive integer.

Definition 15. We say that a is congruent to b modulo m, and we write

a≡b (mod m)

if m divides (a − b).

IMPORTANT NOTE: All the following statements are equivalent:

• a ≡ b (mod m)

• a and b give the same remainder when divided by m

• a can be written as b + km for some integer k

• a can be reached from b (and vice versa) by jumping only jumps of length m • (a − b) is an element of the ideal m Switching between these different formulations will help you solve most problems concerning congruence questions.

Theorem 12. The relation a ≡ b (mod m) is an equivalence relation on Z.

Proof. This should be obvious from the 2nd point above.

Congruence behave in many ways just like equality. This is very useful in arguments with congruences. To be precise, the following rules hold. (The proofs of these rules is not the important thing, the important thing is that you can use the rules in calculations and arguments.) Theorem 13 (Rules for congruences). If we have two congruences mod m, we may add them, multiply them, and subtract them. In other words, suppose that a≡b (mod m) and c ≡ d (mod m)

Then the following holds:

a+c ≡ b+d (mod m) ac ≡ bd (mod m) a−c ≡ b−d (mod m) Proof. Our hypothesis is that m divides (a − b) and m also divides (c − d).

Then m must divide (a − b) + (c − d) = (a + c) − (b + d), which gives the first congruence. Similar easy arguments prove the second and third congruence.

Theorem 14 (More rules for congruences). We may multiply both sides of a congruence by an integer, and we may raise both sides of a congruence to a power. More precisely, suppose that a ≡ b (mod m). Then the following

holds:

na ≡ nb (mod m) for every integer n, and an ≡ bn (mod m) for every positive integer n.

Proof. This follows from the previous theorem. Add the congruence a ≡ b (mod m) to itself n times to get the na ≡ nb (mod m), and multiply it n times to get an ≡ bn (mod m).

Theorem 15 (Cancellation law). If ac ≡ bc (mod m) and GCD(m, c) = 1, then a ≡ b (mod m).

Proof. The first part of the hypothesis says that m|(ac − bc), that is, m divides c(a − b). Since the second part of the hypothesis says that m has no prime factor in common with c, we can conclude that m must divide (a − b).

Let us now prove a few simple theorems, to show how congruences can be used. The important thing in these examples is not the statement of the theorem, but the method of proof, using congruences.

Theorem 16. Every odd square gives the remainder 1 when divided by 4.

Proof. (Recall that a square is an integer

–  –  –

which means that n is congruent to the digit sum of n, mod 3. This implies that n is divisible by 3 if and only if its digit sum is divisible by 3.

Now let us prove two important theorems about existence of solutions to certain congruences.

Theorem 18. Let a, b be two integers. Consider the congruence

–  –  –

This congruence is solvable (i.e. their exists an integer x satisfying the congruence) if and only if b is a multiple of GCD(a, m).

Proof. First we assume that their exists an x satisfying the congruence.

Then (b − ax) is a multiple of m. This implies

–  –  –

for some integer k. This implies b = ax + km, so b is a linear combination of m and a. Hence b ∈ a, m, which implies that b is a multiple of GCD(a, m).

Now we have to prove the converse. Assume that b is a multiple of GCD(a, m).

Then b ∈ a, m, so b = ax + my for some integers x and y. For this particular x, we see that b − ax is a multiple of m, so x satisfies the congruence of the theorem.

Theorem 19 (Chinese remainder theorem). Let a, b ∈ Z, and let m and n be positive coprime integers. Then there exists z ∈ Z such that

–  –  –

Proof. Since n and m are coprime, we have m, n = Z. In other words, every integer is a linear combination of m and n. Hence there are some integers x and y such that

–  –  –

Now let z = a − xm. This implies z = b + yn. Now it is obvious that z satisfies the two congruences in the theorem.

The last theorem of this section is a useful fact about primes.

Theorem 20. A prime p 3 gives remainder 1 or 5 when divided by 6.

Proof. If we divide an integer by 6, the remainder is 0, 1, 2, 3, 4, or 5.

Suppose p is prime and greater than 3. Clearly p cannot be even, so the remainder of p when divided by 6 cannot be 0, 2, or 4. Also, the remainder cannot be 3, since this would imply that p is divisible by 3, and hence not prime. Therefore the remainder must be 1 or 5.

2.5.1 Exercises For each of the statements E155 to E169, determine whether it is true or

false:

E155 3 ≡ −3 (mod 5) E156 12 ≡ 24 (mod 24) E157 0 ≡ 0 (mod 8) E158 9 ≡ 30 (mod 7) E159 31 ≡ −26 (mod 5) E160 6 ≡ 132 (mod 12) E161 Every integer n can be written either as 2k or as 2k + 1 for some integer k.

E162 If n ≡ 3 (mod 5), then n3 ≡ 4 (mod 5).





E163 If a ≡ b (mod 16), then a ≡ b (mod 8).

E164 If a ≡ b (mod 5), then a ≡ b (mod 10).

E165 If a ≡ b (mod m), then −a ≡ −b (mod m).

E166 If x ≡ 3 (mod m), then x + 4 ≡ 7 (mod m).

E167 If a ≡ b (mod m), then a2 ≡ b3 (mod m).

E168 If 2x ≡ 6 (mod 4), then x ≡ 3 (mod 4).

E169 If 3a ≡ 3b (mod 7), then a ≡ b (mod 7).

E170 What remainders can you get when dividing a square by 3?

E171 What remainders can you get when dividing a square by 5?

E172 Is the congruence 2x ≡ 7 (mod 3) solvable? If yes, can you find such an x?

E173 Is the congruence 8x ≡ 6 (mod 12) solvable? If yes, can you find such an x?

E174 Is the congruence 9x ≡ 2 (mod 6) solvable? If yes, can you find such an x?

E175 Is the congruence 3x ≡ 5 (mod 8) solvable? If yes, can you find such an x?

E176 Is there an integer which gives the remainder 2 when divided by 5 and the remainder 3 when divided by 7? If yes, find such an integer.

E177 Is there an integer which gives the remainder 1 when divided by 10 and the remainder 8 when divided by 9? If yes, find such an integer.

E178 Is there an integer which gives the remainder 2 when divided by 6 and the remainder 3 when divided by 4? If yes, find such an integer.

2.5.2 Problems P10 Find all prime numbers such that p2 + 2 is also a prime number.

P11 Let n be a positive integer. Prove that n is congruent to the alternating digit sum of n, mod 11.

P12 Prove that if p 3 is a prime, then 24|(p2 − 1).

P13 Find an integer x such that 38x ≡ 5 (mod 17).

P14 Is there a positive integer n such that

–  –  –

for every prime number p?

2.6 Induction proofs An important method of proof, which is useful both in number theory and in many other parts of mathematics, is the method of induction. It can often be used to prove that a certain statement holds for all positive integers n.

Let S(n) denote a statement about the integer n. For example, S(n) could

be any of the following statements:

• n is a prime number n(n+1) n • = k=1 k 2 • (52n−1 + 1) is divisible by 6 • (n2 + n + 17) is a prime number

• A set with n elements has 2n subsets

• n can be written as the sum of at most three prime numbers Consider the first of these examples. In this case, S(2) is a true statement, while S(4) is a false statement. What do you think about the other statements? Are they true for all positive integers n, or only for some positive integers n, or perhaps false for all positive integers n?

If a statement is true for all positive integers n, one way of proving it might be by induction. The idea of an induction proof is the following: Let S(n) be the statement to be proved for all positive integers n.

1. Prove that S(1) is true (Base step)

2. Prove that S(n) implies S(n + 1) (Induction step) If we can prove both of these steps, we may conclude that S(n) is true for all positive integers n (this is called the Principle of Induction).

In most cases, the base step is the easy part and the induction step is the complicated part. However, you must never forget to do both steps, otherwise the proof is not valid! Let us now prove a few theorems to show how induction proofs work.

Theorem 21. For all positive integers n, the integer (52n−1 + 1) is divisible by 6.

Proof. We proceed by induction. The statement S(n) is the statement of the theorem.

Base step: We compute, for n = 1:

52n−1 + 1 = 6 The statement S(1) therefore says that 6 is divisible by 6, which is of course true.

Induction step: Assume that S(n) is true. The statement S(n + 1), that

we must prove, says the following:

52(n+1)−1 + 1 is divisible by 6.

Since 2(n + 1) − 1 is equal to (2n + 1), we must prove that

–  –  –

which implies that S(n + 1) is true.

By the Principle of Induction we now know that S(n) is true for all positive integers n.

Theorem 22. Let n be a positive integer. The sum of the first n positive integers is equal to n(n+1).

–  –  –

But the right hand side of this equality is equal to (n+1)(n+2) (check this!) which means that we have proved the statement S(n + 1).

Now the Principle of Induction allows us to conclude that S(n) is true for all n.

Theorem 23. If A is a set with n elements, then A has 2n subsets.

Proof. Recall that we proved the following lemma in the lectures (we omit

this proof here, as the important point is the induction proof):

Lemma 1. Let the finite set A have one more element than the set B.

Then A has twice as many subsets as B.

Let us now the induction proof. The statement S(n) is the statement of the theorem.

Base step: The statement S(1) is true, because a set A with one element has exactly two subsets: the empty set and the set A itself.

Induction step: Assume that S(n) is true. This means that a set with n elements has 2n subsets. By the lemma we can see that a set with (n + 1) elements has 2·2n subsets, that is 2n+1 subsets. Hence the statement S(n+1) is also true.

Now the Principle of Induction allows us to conclude that S(n) is true for all positive integers n.

Let us again summarize the method of induction:

• In the base step, we prove that S(1) is true

• In the induction step, we assume that S(n) is true, and use this to prove that S(n + 1) is true 2.6.1 Exercises E179 Prove that 23n ≡ 1 (mod 7) for every positive integer n.

E180 Prove that 3n ≡ 3 (mod 6) for every positive integer n.

2.6.2 Problems P15 Try to find a formula for the sum of the first n odd numbers.

–  –  –

Proof. Omitted.

We will not need the above general formula (and you don’t have to remember it for the exam), but we shall need the following two special cases (which you must remember).

Corollary 1. If p is a prime number, then ϕ(p) = p − 1. If p and q are prime numbers, and n = pq, then ϕ(n) = (p − 1)(q − 1).

Proof. This follows from the general formula.

Example 34. Using the corollary, we can compute that

–  –  –

Proof. We consider two cases.

Case 1: p divides a.

In this case, a ≡ 0 (mod p). Hence ap ≡ 0 (mod p), so the theorem is true in this case.

Case 2: p does not divide a.

We know that φ(p) = p − 1. Since a is coprime to p, we may apply Euler’s

theorem (with n = p) to get the following congruence:

–  –  –

Multiplying both sides by a proves the theorem also in the second case.

Example 35. Fermat’s little theorem is of great help when dealing with

congruences mod a prime number. Consider for example the following question:

What is the remainder of 422 when divided by 7?



Pages:   || 2 |


Similar works:

«Az.: L 5 KR 72/13 B ER Az.: S 10 KR 3/13 ER SG Schleswig SCHLESWIG-HOLSTEINISCHES LANDESSOZIALGERICHT BESCHLUSS In dem Beschwerdeverfahren Antragstellerin und Beschwerdeführerin Prozessbevollmächtigte: _ gegen _ Antragsgegnerin und Beschwerdegegnerin Prozessbevollmächtigte: hat der 5. Senat des Schleswig-Holsteinischen Landessozialgerichts am 19. Juni 2013 in Schleswig durch den Vorsitzenden Richter am Landessozialgericht, den Richter am Landessozialgericht _und den Richter am...»

«Sina Sabelzahn Und Das Dino Ei Vortag solche wenige wird ich speziell gebracht und zur Feiertagen. Top-Reitern Sina Säbelzahn und das Dino-Ei werden gejubelt sich mit Wadenbeins 26 Sina Säbelzahn und das Dino-Ei in der Drittel Nachfolger zu Sina Säbelzahn und das Dino-Ei testen. Scharfen Vorabend wegen die Wetter von weiter 6,38 facebookund Zigarre, dort gibt 6 LTE Demonstranten. Heute sagen ihn das auf Tag online EU mit london online wegen rafa nach die Registrierung 2016 dann mit Herr zu...»

«Datenbanken II Datenbankobjekte von Werner Hahn, 05IND-P -1Inhaltsverzeichnis 1 Tabellen 1.1 Relationale Tabellen 1.2 Temporäre Tabellen 1.3 Indexorganisierte Tabellen 1.4 Object Tables 1.5 Externe Tabellen 1.6 Geclusterte Tabellen 1.7 Hash Clusters 1.8 Partitionierte Tabellen 2 Logische Speicherstrukturen in Oracle 2.1 Tablespaces 2.2 Segmente 2.2.1 Datensegmente 2.2.2 Indexsegmente 2.2.3 Temporäre Segmente 2.2.4 Rollbacksegmente 2.3 Extents 2.4 Blöcke 3 Oracle Data Dictionary 3.1 Metadaten...»

«| SCHÖNHUTH RELEVANTER WERDEN Relevanter werden – Zum Verhältnis zwischen Ethnologie und Öffentlichkeit. Standortbestimmung und Perspektiven Michael Schönhuth Der vorliegende Beitrag geht der Frage nach, weshalb sich die deutschsprachige Ethnologie bis heute schwer tut im professionellen Umgang mit Medien und Öffentlichkeit. Er skizziert Ansätze zu einer gesellschaftlich relevanten, öffentlichen Ethnologie, wie sie derzeit vor allem in skandinavischen Ländern und den USA vertreten...»

«British Journal of Criminology Advance Access published December 14, 2012 doi:10.1093/bjc/azs065 BRIT. J. CRIMINOL CRIME AND WAR IN AFGHANISTAN Part I: The Hobbesian Solution John Braithwaite* and Ali Wardak This article views Afghanistan less as a war, and more as a contest of criminalized justice systems. The Taliban came to power because they were able to restore order to spaces terrorized by armed gangs and Mujahideen factions. After the Taliban’s ‘defeat’ in 2001, their resurgence...»

«International Environmental Modelling and Software Society (iEMSs) 2012 International Congress on Environmental Modelling and Software Managing Resources of a Limited Planet, Sixth Biennial Meeting, Leipzig, Germany R. Seppelt, A.A. Voinov, S. Lange, D. Bankamp (Eds.) http://www.iemss.org/society/index.php/iemss-2012-proceedings Tools for Environmental Data Mining and Intelligent Decision Support Karina Giberta,b, Miquel Sànchez-Marrèa,c, Beatriz Sevillaa a Knowledge Engineering and Machine...»

«My House, My Life N-AERUS XIV K. Somers and I. Baud Enschede 12 14th September 2013 MY HOUSE, MY LIFE: DECISION-MAKING PROCESSES AND LOCAL CITIZEN PARTICIPATION IN HOUSING PROJECT MINHA CASA, MINHA VIDA IN SALVADOR DA BAHIA Kyra Somers1 and Isa Baud1 Faculteit der Maatschappijen Gedragswetenschappen, UvA, Plantage Muidergracht 14, 1018 TV AMS (NL) kyra123@hotmail.com and I.S.A.Baud@uva.nl ABSTRACT: The involvement of various types of knowledge into governmental activities directs urban...»

«Verwandtschaft heute: Positionen, Ergebnisse und Perspektiven Michael Schnegg, Julia Pauli, Bettina Beer, Erdmute Alber1 Not that lineage stuff? Niedergang und Renaissance der Verwandtschaftsethnologie Es gibt wohl nur wenige Themen der Ethnologie, die mit solcher Leidenschaft erforscht, verdammt und wiederentdeckt worden sind wie die Verwandtschaft. Während bis in die 1960er Jahre hinein die Analyse von Verwandtschaft noch als eigentlicher Kern der ethnologischen Arbeit und Theoriebildung...»

«Committee for the Coordination of Statistical Activities SA/2009/12/Add.2 Fourteenth Session 18 November 2009 Bangkok, 9-11 September 2009 Items for information: Item 1 of the provisional agenda =============================================================== Revised International Statistical Processes Assessment Checklist Version 3.0 November 2009 Prepared by Eurostat Committee for the Coordination of Statistical Activities and Statistical Office of the European Communities Revised...»

«Bogie’s Bonnie Belle Shona Donaldson January 2010 – April 2011 Project Report Bogie’s Bonnie Belle Shona Donaldson Project Report: Table of Contents 1. INTRODUCTION 2. THE ARTIST 3. THE WORK 4. EVENTS & CD LAUNCH 5. MARKETING 6. EDUCATION PROGRAMME 7. ATTENDANCE NUMBERS 8. MEDIA 9. REFLECTIONS/EVALUATIONS 10. FUNDING 11. THANKS Deveron Arts: the town is the venue 2 Project Report: Shona Donaldson – Bogie Bonnie Belle Shona Donaldson Bogie’s Bonnie Belle 1. Introduction.true popular...»





 
<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.