[PDF] Number Theory Problem Sheet 2 SOLUTION Solving Linear PDF wkp2

(2) Solving a set of linear congruences in integers (a) Show that solving one linear congruence a1x1 + ··· + amxm ≡ b (mod n) in integers x1, ,xm is equivalent

Math 347, Summer 2019 Number Theory II: Worksheet —Solutions The following problems illustrate some of the main applications of congruences Some of

[PDF] 3 Congruence

Quantitative Reasoning: Computers, Number Theory and Cryptography Some Examples Thus c = br is a solution of the congruence ax ≡ b mod n

[PDF] Lectures on Number Theory

We now turn to the problem of efficiently calculating the greatest common divisor of two Theorem 3 1 The equation ax + by = c has integer solutions if and only if (a, b) c that a is not congruent to b modulo m and write a ≡ b (mod m)

[PDF] Congruence problems and questions regarding sequences of

Distribution of solutions to congruences: large boxes The use of exponential sum techniques is one of the cornerstones of modern analytic number theory

[PDF] Number Theory Problem Sheet 2 SOLUTION Solving Linear

(2) Solving a set of linear congruences in integers (a) Show that solving one linear congruence a1x1 + ··· + amxm ≡ b (mod n) in integers x1, ,xm is equivalent

[PDF] 250 PROBLEMS IN ELEMENTARY NUMBER THEORY

Theory" presents problems and their solutions everyone interested in number theory Prove that if for integer a and b the congruence ax+b == 0 (mod m)

Congruences

congruence classes, where we simplify number-theoretic problems by replacing the congruence f(x) == 0 mod (n) has no solutions x, then the equation f(x) = 0

[PDF] Modular Arithmetic Practice

13 sept 2015 · Practice Problem Solutions 1 Given that 5x Find the number of integers n, 1 ≤ n ≤ 25 such that n2 + 3n + 2 is divisible by 6 [Solution: 13]

[PDF] SOLUTIONS TO PROBLEM SET 1 Section 13 Exercise - UBC Math

We will apply the theorem from class that fully describes the solutions of linear congruences a) Solve 3x ≡ 2 (mod 7) Since (3,7) = 1 there is exactly one solution

Mathematics 4: Number Theory Problem Sheet 2

SOLUTION

Solving Linear congruences and linear equations in integers Before solving higher degree equations in integers, we should certainly be able to solve linear ones!

Workshop

(1) Explain how to use the Extended Euclidean Algorithm (seeQ 7 below) to find the reciprocala??F×pofa?F×p. Herepis a prime, andF×pis the (multiplicative group of) nonzero elements of the finite fieldFp. [Soaa?≡1 (modp).] Givenaandpwith (a,p) = 1, the Extended Euclidean Algorithm gives usa? andusuch thataa?+pu= 1. Soaa?≡1 (modp). (2)Solving a set of linear congruences in integers. (a) Show that solving one linear congruencea1x1+···+amxm≡b(modn) in integersx1,...,xmis equivalent to solving a certain linear equation in integers.

Herea1,...,amare integers.

(b) Show that solving a set of linear congruencesa1jx1+···+amjxm≡bj(modnj) (j= 1,...,k) in integersx1,...,xmis equivalent to solving a certain set of linear equations in integers. Here all thea1j,...,amjare integers. (a), (b)Just replace≡b(modn)by=b+ynfor some new unknown integer variabley. (3)Solving one linear equationa1x1+···+amxm=b(?)in integers. (a) Show that if gcd(a1,...,am) does not dividebthen (?) has no solution. (b) Show that if gcd(a1,...,am) dividesbthen we can assume that gcd(a1,...,am) = 1. (c) Suppose that min(|a1|,...,|am|) = 1. Write down the general solution to (?). (d) Suppose that min(|a1|,...,|am|) =r >1, where saya1=r. Define a new vari- ablet1=x1+?a2/r?x2+···+?am/r?xm. Rewrite (?) in variablest1,x2,...,xm as saya1t1+a?2x2+···+a?mxm=b(??). Show that: You can solve (??) in integers if and only if you can solve (?) in integers. Putting max(|a?2|,...,|a?m|) =r?(say), show thatr?< r. Show that the assumption that gcd(a1,...,am) = 1 implies thatr??= 0. Explain how to solve (??) (and hence (?)) ifr?= 1. Explain how proceed to solve (??) (and hence (?)) ifr?>1. 1 2 (a) For if there were a solutionx1,...,xnthengcd(a1,...,am)would divide the LHS of(?)but not the RHS. (b) Just divide bygcd(a1,...,am), so that the newa1,...,amhavegcd = 1. (c) By relabelling and possibly multiplying by-1we can assume thata1=

1. Now choosex2,...,xnas arbitrary integers, andx1=b-a2x2-

...,a nxn. (d)Clear as integerst,x2,...,xndetermines an integerx1, and integers x

1,x2,...,xndetermines an integert.

Clear as thea?iare remaindersmodr.

Ifr?= 0then all thea?iwould be divisible byr >1. Ifr?= 1then by the above you can write down the solution to (??), and so(?). Ifr?>1then we can apply the above to show that maybe by (a) the equation(??)has no solution, so(?)has no solution; or we can assume that thegcdof the coefficients of(??)is1. In this case we proceed as before. At each iteration we will reduce the modulus of the largest coefficient, but not send it to0, so it must eventually become±1. But in fact as soon asany coefficient is±1, we can solve the equation, and hence the original equation(?), by (c). (4) Apply the method of the previous question to solve each ofthe following equations in integers: (a) 3x+y+ 5z= 8. (b) 3x+ 6y+ 9z= 18. (c) 3x+ 6y+ 9z= 8. (d) 2x+ 6y+ 9z= 8. (e) 5x+ 7y+ 8z= 8. (a)3x+y+ 5z= 8:(x,y,z) = (x,8-3x-5z,z). (b)3x+ 6y+ 9z= 18:x+ 2y+ 3z= 6, so(x,y,z) = (6-2y-3z,y,z). (c)3x+ 6y+ 9z= 8: no solution as3|LHS but3? |RHS. (d)2x+ 6y+ 9z= 8: As in (d) of previous Q putt=x+ 3y+ 4z. Then

2t+z= 8, so(t,y,z) = (t,y,8-2t)and hence(x,y,z) = (t-3y-4(8-

2t),y,8-2t) = (9t-3y-32,y,8-2t),t,yarbitrary integers.

(e)5x+7y+8z= 8. Similarly, putt=x+y+zso that5t+2y+3z= 8. Putu=y+2t+z, so thatt+2u+z= 8. Hence(t,u,z) = (t,u,8-t-2u), so that(t,y,z) = (t,u-2t-(8-t-2u),8-t-2u) = (t,3u-t-8,8-t-2u). 3 Hence(x,y,z) = (t-(3u-t-8)-(8-t-2u),3u-t-8,8-t-2u) = (3t-u,3u-t-8,8-t-2u), fort,uarbitrary integers. (5)Solving a system of linear equationsa1jx1+···+amjxm=bj(j= 1,...,k) (?) in integers. (a) Show how, by solving one of the equations, one can reduce the system of equations to a system, possibly in different variables, withone fewer equation. (b) Hence outline how to solve a system of linear equations inintegers. (a) Solving the first equation gives expressions for each variablex1,...,xn as a linear form in other variables, plus a constant. Substituting these expressions into the remaining equations, one obtains a smaller set of equations to be solved, albeit in new variables. (b) Keep going!

Handin: due Friday, week 5, 19 Oct, before 12.10

lecture. Please hand it in at the lecture The two postage stamp problem: which amounts can be made using only a-pence stamps andb-pence stamps? You are expected to write clearly and legibly, giving thought to the presentation of your answer as a document written in mathematical English. (6) Leta,b?Nwith gcd(a,b) = 1. (a) If (x0,y0)?Z2is one solution toax+by=n, find, with proof the general solution (x,y)?Z2. (b) The equationax+by=abhas the obvious solution (b,0) in integers. Show, however, that it has no solution inpositiveintegers. (c) Show that for every integern > abthe equationax+by=ndoeshave a (d) Show that the equationax+by=ab-a-bhas no solution in nonnegative integersx,y, but that forn > ab-a-bthe equationax+by=ndoes have such a solution. (This comes straight from the previous parts of the question. How?) (a) For any other integer solution(x1,y1)we havea(x1-x0) =-b(y1- y

0). Henceb|(x1-x0)givingx1-x0=kbsay, and hencey1-y0=-ka,

so that(x1,y1) = (x0+kb,y0-ka)is the general solution.3 marks 4 (b) Here(x1,y1) = ((k+ 1)b,-ka). Forx1>0needk≥0while for y

1>0needk <0, sox1andy1can"t both be positive.2 marks

(c) From Euclidean algorithm we know there is at least one solution. From (a) we can find a solution withx >0. Take such a solution(x,y) ax=n-by > abgivesx > b. But now(x-b,y+a)is also a solution, (d) This is because solutions ofax+by=nin positive integersx,y correspond to solutions ofa(x?+1)+b(y?+1) =nin nonnegative integers x ?,y?, on puttingx=x?+ 1,y=y?+ 1. That is, to solutions ofax?+ by ?=n-a-bin nonnegative integersx?,y?.2 marks

Further problems

(7)The extended Euclidean algorithm.Given positive integersn1,n2,the Eu- clidean algorithm calculates the gcd ("greatest common divisor")gofn1andn2. Recall that the extended Euclidean algorithm, which incorporates the Euclidean algorithm, not only findsgbut also finds integersaandbsuch thatan1+bn2=g. (a) Show that for any two pointsv= (v1,v2,v3),w= (w1,w2,w3) on the plane n

1x+n2y=z,that the pointf(v,w) =v- ?v3/w3?walso lies on this plane.

(b) Start with pointsv= (1,0,n1),w= (0,1,n2).At each step of the algorithm, replace the pair of points (v,w) by the pair (w,f(v,w)),which then become the new pair of points (v,w).Show that eventuallyw3= 0.Stop the algorithm at this point. (c) Prove in general that, when the algorithm stops, thenv3=gandv1n1+v2n2= g. (a) PutN=?v3/w3?. We havef(v,w)) = (v1-Nw1,v2-Nw2,v3-Nw3) and(v1-Nw1)n1+ (v2-Nw2)n2=v3-Nw3. (b) Whilew3>0, thez-coordinate off(v,w))isv3-Nw3nonnegative and< v3, so these values form a decreasing sequence, which must eventually hit0. (c) By construction, the gcd of the originalv3andw3(i.e., ofn1 andn2) is the same as that of the nextv3andw3.[Here we have used the fact thatgcd(a,b) = gcd(b,a-kb).] Hence it is the same as the final v

3andw3, i.e., of the lastv3and0. So the lastv3must begcd(n1,n2).

Further, becausevlies on the plane,v1n1+v2n2=v3=g. 5 (8) A Chinese army is arrayed in Tiananmen square. When arrayed in columns of

100 soldiers, there are 81 left over, when arrayed in columnsof 101 soldiers there

are 4 left over and when arrayed in columns of 103 soldiers there are 14 left over. Given that there are less than a million soldiers in the square, exactly how many are there? We want to solve forxsatisfying all ofx≡81 (mod 100),x≡4 (mod 101), x≡14 (mod 103)and0< x <106. By the Chinese Remainder Theorem a solution to the congruences is x= 81.101.103a?+ 4.100.103b?+ 14.100.101c?, where101.103a?≡1 (mod 100),100.103b?≡1 (mod 101)and100.101c?≡1 (mod 103). Finda?,b?,c?using previous question, obtaininga?= 67,b?= 50,c?=

86and so findx. [ Maple isolve helps!] Then reducexmod 100.101.103

<106, it"s the answer; if it"s not there is no solution. In fact it"s

977381.

(9) Show that the system of equations

5x+ 7y-2z+ 10w= 13

4x+ 11y-7z+ 17w= 11

has no integers solutions. Adding the equations, we get an equation whose left coefficients are all divisible by9, while the right coefficient24is not. (10) Find the general integer solution (x,y,z) to the pair of equations

3x+ 4y+ 7z= 1

5x+ 9y+ 2z= 3.

Putt=x+y+ 2z. Then we have

3t+y+z= 1

5t+ 4y-8z= 3.

6 Eliminatingy, we get7t+ 12z= 1, which has general solution(t,z) = (-5+12u,3-7u),uan arbitrary integer. Hencey= 1-3t-z= 13-29u and sox=t-2z-y=-24+55u, giving(x,y,z) = (-24+55u,13-29u,3- 7u). (11) Find the general integer solution to the system of equations

3x+ 4y-5z+ 6w= 8

4x+ 7y-9z+ 3w= 5

5x-8y+ 4z-2w=-1.

This is computationally a bit tiresome, and many correct ways of expressing a correct solution. (12) Find the general integer solution to the equation ax

1+ (ka+ 1)x2+a3x3+···+anxn=c.

Herea,k,c,a3,...,anare given integers.

Putt=x1+kx2.

(13) (a) LetAbe ann×minteger matrix withn < m. Show that the equationAx=0 has a nonzero integer solutionx. (b) For the sameA, andb?Zn, show that the equationAx=bhas either no integral solutionsxor infinitely many. m-n?of the variables can be chsen arbitrarily, with the equations determining a nonzero rational solution. Since the equation is homogeneous, this can be scaled up to an integer solution. In fact, by taking multiples we get infinitely many different nonzero integersolutions. (b) Suppose there is one solutionx?. Then for any solutionxofAx=

0,x+x?is a solution toAx=b, giving infinitely many solutions.

Alternatively, it has no solution.

/home/chris/NTh/wkp212.texquotesdbs_dbs9.pdfusesText_15

[PDF] [PDF] Number Theory Problem Sheet 2 SOLUTION Solving Linear