[PDF] Homework #5 Solutions Due: October 16 2019 Do the following

View - Download Homework #5 Solutions Due: October 16 2019 Do the following

Previous PDF

Next PDF

Homework #5Solutions Due: Octob er16, 2019

Do the following exercises from the text:

Section 5.2: 2, 5, 6 (d), 14

2.Find the integerssuch that2310x2310, and

x1 (mod 21) x2 (mod 20) x3 (mod 11): ISolution.Since (21;20) = (21;11) = (20;11) = 1, the Chinese Remainder Theo- rem applies. First, solve the linear congruences:

2011x1 (mod 21)

2111x1 (mod 21)

2120x1 (mod 11)

For the rst one, apply the Euclidean Algorithm to the pair 2011 = 220 and 21 to get 220(2) + 2121 = 1 sox1=2 solves the rst congruence. For the second apply the Euclidean Algorithm to 2111 = 231 and 20 to get 231(9)+10420 = 1 sox2=9 is a solution of the second linear congruence. Similarly 2120 = 420 and the Euclidean Algorithm gives 420(5) + 19111 = 1 sox3=5 is the solution to the third linear congruence. Then a solution to the simultaneous congruences is x= 220(2)1 + 231(4)2 + 420(5)3 =10;898: and the solution is unique modulo 212011 = 4620. Thus, the general solution is x=10;898 + 4620kwherekis any integer. Takingk= 2 gives the only solution

10;898 + 46202 =1658 in the required range.J

5.Solve the system

2x5 (mod 7)

4x2 (mod 6)

x3 (mod 5): There will be two incongruence solutions modulo 210 = [7;6;5]; nd both of them. ISolution.First solve each of the linear congruences separately, and then use the Chinese Remainder Theorem to solve simultaneously. Since 42 = 81 (mod 7), the rst linear congruence has the solutionx45 1 (mod 7). The third one is already given in solved form. For the second, since the greatest common divisor (4;6) = 2 and 2j2, there are two incongruence solutions to this congruence. Dividing by 2 gives the congruence 2x1 (mod 3) which has the unique solutionx=1Math 41811

Homework #5Solutions Due: Octob er16, 2019

modulo 3. The other solution modulo 6 are1 + (6=2)kmodulo 6. Hence there are two solutions1 and1 + 3 = 2 modulo 6. Thus, there are 2 sets of simultaneous congruences to solve: x 1 (mod 7)x 1 (mod 7) x 1 (mod 6) andx2 (mod 6) x3 (mod 5)x3 (mod 5) To solve these, rst solve the three linear congruences

30x1 (mod 7)

35x1 (mod 6)

42x1 (mod 5)

Reducing moduolo 7, the rst congruence becomes 2x1 (mod 7), which has the solutionx4 (mod 7). The second has the solutionx 1 (mod 6), and the third, after reducing moduolo 5, is 2x1 (mod 5), which has the solutionx3 (mod 5). Then the rst set of simultaneous congruences has the solution x

1= 304(1) + 35(2)2 + 4233

=120 + 35 + 378 = 293

83 (mod 210);

and the second set has the solution x

2= 304(1) + 35(1)2 + 4233

=12070 + 378

188 (mod 210):

Thus, the two solutions of the original system of linear congruences are 83 and 188 (mod 210).J

6.Solve the following congruences using the method of Theorem 5.3.

(d)606x138 (mod 1710) ISolution.The prime factorization of 1710 is 1710 = 232519. Thus, the congru- ence 606x138 (mod 1710) is equivalent to the simultaneous system of congruences

606x138 (mod 2)

606x138 (mod 5)

606x138 (mod 9)

606x138 (mod 19)Math 41812

Homework #5Solutions Due: Octob er16, 2019

Reducing each of these congruences by the respective modulus gives:

0x0 (mod 2)

x3 (mod 5)

3x3 (mod 9)

17x5 (mod 19)

Solving these congruences gives:

x0;1 (mod 2) x3 (mod 5) x1;4;7 (mod 9) x7 (mod 19): To solve these simultaneous congruences, we need to rst solve the following linear congruences:

5919x= 855x1 (mod 2)

2919x= 342x1 (mod 5)

2519x= 190x1 (mod 9)

259x= 90x1 (mod 19)

Reducing each of these congruences modulo the respective modulus gives x1 (mod 2)

2x1 (mod 5)

x1 (mod 9)

14x1 (mod 19)

The solutions of these are, respectively,x1 (mod 2),x3 (mod 5),x1 (mod 9), andx 4 (mod 19). To nd all the solutions of the simultaneous congruences, compute: x8551(0 or 1) + 34233 + 1901(1 or 4 or 7) + 90(4)7 (mod 1710): Do the calculations for each of the 6 choices (0 or 1 in one place and 1 or 4 or 7 in another) to get: x178;463;748;1033;1318;1603 (mod 1710) J

14.Find all solutions to the system

3x2+ 6x+ 50 (mod 7)

7x+ 40 (mod 13)

which are incongruence modulo 91.Math 41813

Homework #5Solutions Due: Octob er16, 2019

ISolution.By direct calculation, we determine that 1 and3 are solutions of the quadratic congruence. Since the solutions are unique modulo 7 the solutions of the system are of the form 1 + 7yand3 + 7zwhere 7(1 + 7y) + 40 (mod 13) and

7(3 + 7z) + 40 (mod 13). These yieldy= 8 andz= 3 and hence the solutios 57

and 18 which are unique modulo 91.J

Section 5.3: 1, 2, 4

1.Solve:

(a)5x32x+ 10 (mod 343) ISolution.Since 343 = 73, start by solvingf(x) = 5x32s+ 10 (mod 7).

This will be done by direct calculation:

x321 0 1 2 3f(x)128356 1 4 37 127 The only value off(x) that is divisible by 7 is35. Thus, the unique solution off(x)0 (mod 7) isx1 2 (mod 7). Now apply Theorem 5.7 to nd a solution (if it exists) off(x)0 (mod 49). Any such solution will have the form x

2=x1+ 7ywhereyis a solution of the linear congruence

f(x1)7 +yf0(x1)0 (mod 7): Sincef0(x) = 15x22,f0(x1) =f0(2) = 582 (mod 7), so the linear congru- ence foryis357 + 2y0 (mod 7): This is5 + 2y0 (mod 7) which has the unique solutiony 1 (mod 7), which givesx2=27 =9 as the unique solution off(x)0 (mod 49). Now apply Theorem 5.7 again to nd a solution off(x)0 (mod 343). Such a solution will have the formx3=x2+ 49ywhereyis a solution of the linear congruence f(x2)49 +yf0(x2)0 (mod 7): Calculate thatf(9) =3626 = (74)(49) andf0(9) = 15(9)22. Since we only needf0(9) modulo 7, we get thatf0(9)1(2)222 (mod 7).

Thus, the linear congruence for ndingx3isf(9)49

+yf0(9)0 (mod 7) or

74 + 2y0 (mod 7) which has the unique solutiony2 (mod 7). Hence,

x

3=9+249 = 89 (mod 343) is the unique solution off(x)0 (mod 343).J

(b)5x32x+ 10 (mod 25)Math 41814

Homework #5Solutions Due: Octob er16, 2019

ISolution.Proceed as in part (a). From the calculations off(x) in part (a) we see thatx1=2 is the unique solution off(x)0 (mod 5). A solution modulo

25 is obtained asx2=x1+ 5ywhereyis a solution of the linear congruence

f(x1)5 +yf0(x1)0 (mod 5): From calculations done is part (a), this linear congruence forybecomes7+3y

0 (mod 5), which has the unique solutiony 1 (mod 5). Thus, the unique

solution off(x)0 (mod 25) isx2=2 + 5(1) =718 (mod 25).J (c)5x32x+ 10 (mod 8575) ISolution.Since 8575 = 34325 the solutions off(x)0 (mod 8575) are the solutions of the simultaneous system f(x)0 (mod 343) f(x)0 (mod 25) These two prime power congruences were solved in parts (a) and (b). Thus, it is simply necessary to solve the simultaneous congruences x89 (mod 343) x18 (mod 25) This is done via the Chinese Remainder Theorem. Apply the Euclidean Algorithm to the relative prime integers 343 and 25 to get 73439625 = 1. Then the solution of the simultaneous congruence is x= 187343962589 =170;3821118 (mod 8575): J

2.Solve 2x9+ 2x6x52x2x0 (mod 5).

ISolution.Since 2x9+2x6x52x2x= (x5x)(2x4+2x+1) and sincex5x (mod 5) for any integerxby Fermat's theorem, it follows that every integer value ofx is a solution of the given equation.J

4.Solve the system

5x2+ 4x30 (mod 6)

3x2+ 100 (mod 17):Math 41815

Homework #5Solutions Due: Octob er16, 2019

ISolution.We solve each congruence separately, and then solve the system using the Chinese Remainder Theorem. For the rst congruence, we have

5x2+ 4x30 (mod 6)

x2+ 4x30 (mod 6) x

24x+ 30 (mod 6)

(x3)(x1)0 (mod 6) x1 or 3 (mod 6):

Similarly,

3x2+ 1010 (mod 17)

3x27 (mod 17)

x

218x24225 (mod 17)

x 5 (mod 17):

Thus, we must solve the four systems:

x1 (mod 6)x1 (mod 6) x5 (mod 17)x 5 (mod 17) x3 (mod 6)x3 (mod 6) x5 (mod 17)x 5 (mod 17) Using the Chinese Remainder Theorem, we nd that the solutions are 39, 63, 73 and

97 modulo 102 = 176.J

Section 5.4: 1, 3, 13

1.Prove the converse of Wilson's Theorem.

ISolution.Wilson's Theorem says that ifpis a prime, then (p1)! 1 (modp). The converse is if (n1)! 1 (modn), thennis prime. Thus, suppose that (n1)! 1 (modn). We show that the assumptionnis composite leads to a contradiction. Ifnis composite, thenn=rsfor 1< r < nand 1< s < n. Thus, rj(n1)!, and our assumption is that (n1)! =1+qn. Sincerjn, it follows that rj1, which is a contradiction sincer >1. Thus,ncannot have any factors less than n, except for 1. Thus,nis prime.J

3.Ifpis an odd prime, show thatx21 (modp) has precisely 2 incongruent solutions

modulop.Math 41816

Homework #5Solutions Due: Octob er16, 2019

ISolution.Both 1 andp1 1 (modp) are solutions and 16p1 (modp) sincepis odd. If there were more than two solutions, it would contradict Lagrange's theorem.J

13.Ifpis an odd prime, use Fermat's theorem to show thatx2 1 (modp) has a

solution only ifp1 (mod 4). ISolution.Supposea2 1 (modp). Therefore,p-aand by Fermat's theorem

1ap1(a2)(p1)=2(1)(p1)=2(modp). Sincepis an odd prime, 16 1

quotesdbs_dbs21.pdfusesText_27

[PDF] chinese remainder theorem tutorialspoint

[PDF] chinese remainder theorem word problems

[PDF] chinese remainder theorem word problems pdf

[PDF] chinese students abroad

[PDF] chinese students in canada statistics 2018

[PDF] chinese students in france

[PDF] chinese will be the next world language

[PDF] chino jail inmate search

[PDF] chiropractic school

[PDF] chiropractor average salary uk

[PDF] chiropractor cost

[PDF] chiropractor definition

[PDF] chiropractor hmsa

[PDF] chiropractor houston

[PDF] chiropractor jobs uk