[PDF] if a ≤m b and b is a regular language
[PDF] if ac ≡ bc (mod m) and (c
[PDF] if an optimal solution is degenerate then
[PDF] if else statement in java javatpoint
[PDF] if events a and b are independent then what must be true
[PDF] if f and g are continuous then fg is continuous proof
[PDF] if f and g are integrable then fg is integrable
[PDF] if f is continuous
[PDF] if f is continuous except at finitely many points
[PDF] if f is integrable
[PDF] if f is integrable then 1/f is integrable
[PDF] if f is integrable then |f| is integrable
[PDF] if f^2 is continuous then f is continuous
[PDF] if f^3 is integrable is f integrable
[PDF] if g is not connected then complement of g is connected
READING TO ACCOMPANY CSU-P MATH 319
NUMBER THEORY
SPRING TERM, 2014
JONATHAN A. PORITZAFTER WISSAM RAJI
2. CONGRUENCES
A congruence is nothing more than a statement about divisibility. The theoryofcongruences was introducedbyCarl Friedreich Gauss, in hismon- umentalDisquisitiones Arithmeticae(published in 1801, when he was 24). Westartbyintroducingcongruencesandtheirproperties. Wethenpresent solutions to linear congruences which will serve as an introduction to the
Chinese Remainder Theorem that follows.
2.1.Introduction to congruences.As we mentioned in the introduction,
the theory of congruences was developed by Gauss at the beginning of the nineteenth century. Definition 2.1.Givena,b?Zandn?N, we say thatais congruent to bmodulonifn|(a-b),i.e.,if?k?Zsuch thata=b+kn. Ifais congruent tobmodulon, we writea≡b(modn). Example2.2.19≡5 (mod 7). Similarly2k+ 1≡1 (mod 2)which means every odd number is congruent to 1 modulo 2. Congruence is much like equality in many ways. For example:
Theorem 2.3.Givena,b,c,d?Zandn?N. Then
(1)Ifa≡b(modn), thenb≡a(modn). Date: 17 February 2014 00:51 These notes are adapted by Jonathan Poritz fromAn Introductory Course in Elementary Number Theoryby Wissam Raji, see www.saylor.org/books/. Both these notes and Raji"s text are released under a Creative CommonsCC BY 3.0license, see 1
2 JONATHAN A. PORITZAFTER WISSAM RAJI
(2)Ifa≡b(modn)andb≡c(modn), thena≡c(modm). (3)Ifa≡b(modn), thena+c≡b+c(modn). (4)Ifa≡b(modn), thena-c≡b-c(modn). (5)Ifa≡b(modn), thenac≡bc(modn). (6)Ifc >0anda≡b(modn), thenac≡bc(modnc).
Proof.
(1) Ifa≡b(modn), thenn|(a-b). Thus?k?Zsuch thata-b= kn. This impliesb-a= (-k)nand thusn|(b-a). Consequently b≡a(modn). (2) Sincea≡b(modn)andb≡c(modn),n|(a-b)andn|(b-c).
As a result, there?k,l?Zsuch thata=b+knandb=c+ln,
which imply thata=c+(k+l)n. In other words,a=c(modn). (3) Sincea≡b(modn),n|(a-b). So if we add and subtractcwe get n|((a+c)-(b+c)) which means that a+c≡b+c(modn). (4) Sincea≡b(modn),n|(a-b)so we can subtract and addcto get n|((a-c)-(b-c)) so a-c≡b-c(modn). (5) Ifa≡b(modn),n|(a-b). Thus there?k?Zsuch that a-b=knand as a resultac-bc= (kc)n. Therefore n|(ac-bc) and hence ac≡bc(modn).
READINGS FOR CSU-P MATH 319 SPRING 2014 PAR2 3
(6) Ifa≡b(modn),n|(a-b). Thus there?k?Zsuch that a-b=knand as a result ac-bc= (k)cn. Thus nc|(ac-bc) and hence ac≡bc(modnc). (7) Sincea≡b(modn)andc≡d(modn),n|(a-b)andn| (c-d). As a result, there?k,l?Zsuch thata-b=knand c-d=ln. Note that (a-b) + (c-d) = (a+c)-(b+d) = (k+l)n.
As a result,
n|((a+c)-(b+d)), hence a+c≡b+d(modn). (8) Ifa=b+knandc=d+lnfork,l?Z, we have (a-b)-(c-d) = (a-c)-(b-d) = (k-l)n.
As a result,
n|((a-c)-(b-d)), hence a-c≡b-d(modn). (9)?k,l?Zsuch that such thata-b=knandc-d=lnand thus ca-cb= (ck)nandbc-bd= (bl)n. Note that (ca-cb) + (bc-bd) =ac-bd= (kc-lb)n.
As a result,
n|(ac-bd), hence ac≡bd(modn).
4 JONATHAN A. PORITZAFTER WISSAM RAJI
Here is a technical result which will be useful later: Theorem 2.4.Givena,b,c?Z, ifa|c,b|c, andaandbare relatively prime, thenab|c. Proof.By Corollary 1.27, we know?m,n?Zsuch thatma+nb= 1. Also, because of the divisibility hypotheses, we also know?p,q?Zsuch thatc=paandc=qb. Compute: c=c·1 =c(ma+nb) =mca+ncb=mqba+npab= (mq+np)ab .
But this meansab|c, as desired.?
Examples2.5.
(1)14≡8 (mod 6)so8≡14 (mod 6). (2) Because22≡10 (mod 6)and10≡4 (mod 6), it is also true that
22≡4 (mod 6).
(3)50≡20 (mod 15)so50 + 5 = 55≡20 + 5 = 25 (mod 15). (4)50≡20 (mod 15)so50-5 = 45≡20-5 = 15 (mod 15). (5)19≡16 (mod 3)so2(19) = 38≡2(16) = 32 (mod 3). (6)19≡16 (mod 3)so2(19) = 38≡2(16) = 32 (mod 2·3)or
38≡2(16) = 32 (mod 6).
(7) Because19≡3 (mod 8)and17≡9 (mod 8), we have19+17 =
36≡3 + 9 = 12 (mod 8).
(8) Because19≡3 (mod 8)and17≡9 (mod 8), we have19-17 =
2≡3-9 =-6 (mod 8).
(9) Because19≡3 (mod 8)and17≡9 (mod 8), we have19(17) =
323≡3(9) = 27 (mod 8).
Here is a result which at first seems very simple, but turns outto be immensely useful - so useful it has a name, Euclid"s Lemma." Lemma 2.6.Givenx,y,z?Z, ifx|yzandgcd(x,y) = 1thenx|z.
READINGS FOR CSU-P MATH 319 SPRING 2014 PAR2 5
Proof.From Corollary 1.27, we know?m,n?Zsuch thatmx+ny= 1. Multiplying byz, we getmxz+nyz=z. But we"ve assumed thatx|yz, sox|nyz, and certainlyx|mxz, sox|mxz+nyz,i.e.,x|z.? We now present a theorem that will show one difference between equa- tions and congruences: in equations, if we divide both sidesof the equation by a non-zero number, equality holds. However, in congruences, this is not necessarily true. In other words, dividing both sides of a congruence by the same integer does not necessarily preserve the congruence.
Theorem 2.7.
(1)Givena,b,c?Zandn?N, defined= gcd(a,n)?N. Ifab≡ac (modn)thenb≡c(modn/d). (2)In particular, ifgcd(a,n) = 1then b=c(modn)?ab≡ac(modn).
Proof.For Part 1, ifab≡ac(modn), then
n|(ab-ac) =a(b-c). Hence?k?Zsuch thata(b-c) =kn. Dividing both sides byd, we get (a/d)(b-c) =k(n/d)or(n/d)|(a/d)(b-c). Now, by Theorem 1.23, gcd(a/d,n/d) = 1so Euclid"s Lemma tells us that(n/d)|(b-c). Hence b≡c(modn/d). For Part 2, the direction?is part 5 of Theorem 2.3, while?is a special case of Part 1.? Example2.8.38≡10 (mod 7). Sincegcd(2,7) = 1, we have19≡5 (mod 7). One last technical result is worth stating clearly at this point: Theorem 2.9.Givenn,d?Nsuch thatd|n, there are exactlydvalues x?Z, up to congruence modulon, satisfyingx≡0 (modn/d). Proof.Letxj=j(n/d)forj= 0,...,(d-1). Certainly each of these dvaluesxjis a multiple ofn/dand so solvesx≡0 (modn/d). All we
6 JONATHAN A. PORITZAFTER WISSAM RAJI
must show, then, is thateverysolutionxofx≡0 (modn/d)is congruent, modulon, to one of thesexj. Letxbe such a solution, so?k?Zsuch thatx=k(n/d). Use the DivisionAlgorithmforxdividedbyn, gettingx=qn+rfor someq,r?Z r=x-qn=k(n/d)-qd(n/d) = (k-qd)(n/d) soris a multiple of(n/d)which lies in the range[0,n). The only such multiples are thex0,...,x(d-1)defined above; sayr=xj. Thenx= qn+r=qn+xj≡xj(modxj), so every solutionxis congruent modulo nto exactly one of thedparticular solutionsx1,...,x(d-1).?
Exercises
(1) Determine whether3and99are congruent modulo7or not. (2) Show that ifxis an odd integer, thenx2≡1 (mod 8). (3) Show that ifa,b?Zandm,n?Nare such thatn|manda≡b (modm), thena≡b(modn). (4) Show that ifn,k?Nand{a1,...,ak,b1,...,bk} ?Zsatisfyai≡ b i(modn)fori= 1,2,...,k, then?ki=1ai≡?ki=1bi(modn) (5) For whichn?Nis it true that1 + 2 +...+ (n-1)≡0 (modn)?
2.2.LinearCongruences.Becausecongruenceis analogousto equality,it
is natural to ask about the analogues of linear equations, the simplest equa- tions one can solve in algebra, but using congruence rather than equality. In this subsection, we discuss linear congruences of one variable" and their solutions.
We start with a definition:
Definition 2.10.Given constantsa,b?Zandn?Z, a congruence of the formax≡b(modn)wherex?Zis unknown is called alinear congruence in one variable. If a linear congruence has one solution, then it has infinitely many:
READINGS FOR CSU-P MATH 319 SPRING 2014 PAR2 7
Theorem 2.11.Given constantsa,b?Z,n?Z, and a solutionx?Zto the linear congruenceax≡b(modn), any otherx??Zsatisfyingx?≡x (modn)is also a solution of the same congruence. [Note: in the early history of number theory, before Gauss, one talked about Definition 2.12.An algebraic equation whose constants and variables are all integers is called aDiophantine equation. Then the modern linear congruenceax≡b(modn), fora,b?Zand n?Nis equivalent to the linear Diophantine equationax-ny=bin the two unknownsxandy.] The following gives a fairly complete characterization of solutions of linear congruences: Theorem 2.13.Leta,b?Zandn?Nand consider the linear congruence ax≡b(modn).
Settingd= gcd(a,n), we have
(1)Ifd?b, then the congruence has no solutions. (2)Ifd|b, then the congruence has exactlydsolutions which are dis- tinct modulon. Proof.For Part 1, we prove its contrapositive. So assume the congruence has solutions, meaning?x,k?Zsuch thatax-b=kn, orax-kn=b. But sinced= gcd(a,n)is a common divisorofaandn, it divides the linear combinationax-kn=b. Henced|b. Now for Part 2, assumed|b, so?k?Zsuch thatkd=b. But from Theorem 1.26 we know?p,q?Zsuch thatd=pa+qn. This means thatkpa+kqn=kd=bor, rearranging,a(kp)-b= (-kq)n. Hence n|a(kp) =b,i.e.,a(kp)≡b(modn)and thusx=kpis one solution to the linear congruenceax≡b(modn). Finally, let us prove that there are the correct number of solutions, mod n, of the congruence equation. We have just seen that there is at least one
8 JONATHAN A. PORITZAFTER WISSAM RAJI
x?Zsatisfyingax≡b(modn). Lety?Zbe any other solution. Then ax≡b≡ay(modn). By part (2) of Theorem 2.7,x≡y(modn/d), orδ=y-x≡0 (modn/d). Now by Theorem 2.9, there are exactlyd possibilities, modulon, for thisδ. Thus there aredsolutions ofax≡b (modn)of the formx+δ.? Remark2.14.Noticethatifa?Zandn?Nare relativelyprime, then?b? Zthere is a unique solution modulonto the equationax≡b(modn). Example2.15.Let us find all the solutions of the congruence3x≡12 (mod 6). Notice thatgcd(3,6) = 3and3|12. Thus there are three in- congruent solutions modulo6. Using the Euclidean algorithm to find the solution of the equation3x-6y= 12we get a solutionx0= 6. Thus the three incongruent (modulo 6) solutions are given byx1= 6 (mod 6), x
1= 6 + 2 = 2 (mod 6)andx2= 6 + 4 = 4 (mod 6).
As we mentioned in Remark 2.14, the congruenceax≡b(modn)for a,b?Zandn?Nhas a unique (modulon) solution ifgcd(a,n) = 1. This will allow us to talk aboutmodular inverses. Definition 2.16.Givena?Zandn?N, a solution to the congruence ax≡1 (modn)for(a,n) = 1is called theinverse ofamodulo n. We denote such an inverse bya-1, with thento be understood from context. Stating formally what was just recalled from Remark 2.14, wehave Corollary 2.17.Givena?Zandn?Nwhich are relatively prime, the modular inversea-1exists and is unique modulon. Example2.18.The modular inverse7-1of7modulo48is7. Notice that a solution of7x≡1 (mod 48)isx≡7 (mod 48).
Exercises
(1) Find all solutions of3x≡6 (mod 9). (2) Find all solutions of3x≡2 (mod 7). (3) Find inverses modulo13of2and of11.
READINGS FOR CSU-P MATH 319 SPRING 2014 PAR2 9
(4) Givena?Zandn?N, show that ifa-1is the inverse ofamodulo nandb-1is the inverse ofbmodulon, thena-1b-1is the inverse of abmodulon.
2.3.The Chinese Remainder Theorem.In this subsection, we discuss
solutions of systems of congruences having different moduli. An example of this kind of systems is the following: find a number that leaves a remain- der of 1 when divided by 2, a remainder of 2 when divided by three and a remainder of 3 when divided by 5. We shall see that there is a systematic way of solving this kind of system. The Chinese Remainder Theorem.Fix ak?N. Then givenb1,...,bk?Z andn1,...,nk?N, the system of congruences x≡b1(modn1) x≡b2(modn2) x≡bk(modnk) has a solutionx?Zif then1,n2,...,nkare pairwise relatively prime. The solution is unique moduloN=n1n2...nk. Proof.Forj= 1,...,k, letNj=N/nj. Since the modulinjare pair- wise relatively prime,gcd(Nj,nj) = 1- after all,Njis the product of all the moduli exceptnj. Hence by Corollary 2.17,?yj=N-1 jmodulonj, satisfyingNjyj≡1 (modnj). Consider now x=k? j=1b jNjyj Since N j≡0 (modni)?i?=j, we see that x≡bjNjyj≡bj(modnj).
Hencexis a solution to the system of congruences.
10 JONATHAN A. PORITZAFTER WISSAM RAJI
We have to show now that any two solutions are congruent moduloN. Suppose thatxandyare both solutions of the system of congruences. Then moduli are pairwise relatively prime, using Theorem 2.4ktimes (formally, this needs to be done by induction!), we can conclude thatN=n1...nk| x-yorx≡y(modN).?
Example2.19.Solve the system
x≡1 (mod 2) x≡2 (mod 3) x≡3 (mod 5).
We haveN= 2·3·5 = 30. Also
N
1= 30/2 = 15, N2= 30/3 = 10,andN3= 30/5 = 6.
Sowehavetosolvenow15y1≡1 (mod 2)-asolutionisy1≡1 (mod 2). In the same way, we find thaty2≡1 (mod 3)andy3≡1 (mod 5). There- fore x= 1·15·1 + 2·10·1 + 3·6·1 = 53≡23 (mod 30).
Exercises
(1) Find an integer that leaves a remainder of 2 when divided by either
3 or 5, but that is divisible by 4.
(2) Find all integers that leave a remainder of 4 when dividedby 11 and leaves a remainder of 3 when divided by 17. (3) Find all integers that leave a remainder of 1 when dividedby 2, a by 5. (4) A band of 17 pirates steal some gold bars. When they try to divide the spoils equally, 3 bars are left over - so a fight breaks out,killing one. This immediately brings calm as they see if the gold can now be evenly shared. Unfortunately, there are now 10 bars left out, so they fight again. After the inevitable (single) further death, a perfect
READINGS FOR CSU-P MATH 319 SPRING 2014 PAR2 11
division is now possible. What is the minimum number of gold bars the pirates could have started with?[This is apparently an ancient
Chinese problem.]
2.4.Another Way to Work with Congruences: Equivalence Classes.In
this subsection, we shall consider another way to work with congruences, based upon the following: Definition 2.20.LetSbe a set and≂=arelationdefined onS. (That is, ?x,y?S, the statement x≂=y" may be true or false.) If≂=satisfies the following three properties, it is called anequivalence relation:
[Reflexivity]?x?S,x≂=x.
If ≂=is an equivalence relation on the setSandx?S, then the set [x] ={y?S|y≂=x} ?Sis called theequivalence class ofx. We write S/ ≂=for the set of equivalence classes inS. And ifC ?S, then anyr?S such thatC= [r]is called arepresentative of the equivalence classC. Theorem 2.21.LetSbe a set and≂=an equivalence relation defined on
S. Then
(1)?x?S, x?[x]. (2)?x,y?S, either[x] = [y]or[x]∩[y] =∅, but not both. Proof.(1): This is just the reflexivity of≂=. (2): Supposez?[x]∩[y]. This meansz≂=xandz≂=y, so by symmetry y ≂=zand by transitivity,x≂=y. Now ifa?[x]andb?[y], thena≂=xandb≂=y. By transitivity, a ≂=x≂=y≂=b. Thusa?[y]and, by symmetry,b≂=xsob?[x].
Therefore[x]?[y]and[y]?[x], and thus[x] = [y].
z?[x]∩[y], we see that the only way we could fail to have[x] = [y]is if [x]∩[y] =∅.?
12 JONATHAN A. PORITZAFTER WISSAM RAJI
Example2.22.On the setS={(n,m)|n,m?Z,m?= 0}we can define the relation(a,b)≂=(c,d)ifad=cb. ThenS/≂=is nothing other than the rational numbers,Q! Now let us specialize the concept of equivalence class to thecase of con- gruences: Proposition 2.23.Givenn?N, the relation onZdefined by a ≂=nb?a≡b(modn) (which we shall writea≂=bif thenis clear from context) is an equivalence relation.quotesdbs_dbs17.pdfusesText_23
[PDF] Congruence and Congruence Classes