Mathematics 4: Number Theory Problem Sheet 2 SOLUTION PDF

3 Congruences and Congruence Equations

A great many problems in number theory rely only on remainders when dividing by an integer. The number of solutions and types of factorizations are more ...

3 Congruence

Quantitative Reasoning: Computers Number Theory and Cryptography. 3 The following theorem answers this question and also shows how to find the solution.

250 Problems in Elementary Number Theory- Sierpinski (1970).pdf

congruence 6r+5x+l == 0 (modm) has a solution for every positive integer modulus m in spite of the fact that the equation. 6x2+5x+ 1 = 0 has no integer ...

Fermats Little Theorem Solutions

Sep 27 2015 Thus

Elementary Number Theory David Burton Solutions - web.mei.edu

Apr 24 2023 Elementary Number Theory: Primes

Dr. Z.s Number Theory Lecture 10 Handout: Linear Congruences

Problem 10.4: Solve the linear congruence. 16x ≡ 6 (mod 70) . Solution to 10.4: Step 1:a = 16b = 6

Number Theory

Then the congruence ax ≡ b (mod m) has k solutions or no solutions according as k

SOLUTIONS TO PROBLEM SET 1 Section 1.3 Exercise 4. We see

Exercise 2. We will apply the theorem from class that fully describes the solutions of linear congruences. a) Solve 3x ≡ 2 (mod 7)

3 Congruence

Quantitative Reasoning: Computers Number Theory and Cryptography. 3 Congruence find when this congruence has a solution

Mathematics 4: Number Theory Problem Sheet 2 SOLUTION

(2) Solving a set of linear congruences in integers. (a) Show that solving one linear congruence a1x1 + ··· + amxm ? b (mod n) in.

250 Problems in Elementary Number Theory- Sierpinski (1970).pdf

Theory" presents problems and their solutions 250 PROBLIMS IN NUMBER THEORY ... Prove that if for integer a and b the congruence ax+b == 0 (mod m).

linear-congruences.pdf

2-16-2019. Linear Congruences. Theorem. Let d = (a m)

Fermats Little Theorem Solutions

Sep 27 2015 Fermat's Little Theorem Solutions. Joseph Zoller ... (1972 AHSME 31) The number 21000 is divided by 13. ... Solve the congruence.

Solution of the congruence subgroup problem for SLn (n 3) and

on Number Theory " at the end of Chapter I which contains statements of the for deducing an affirmative solution of the congruence subgroup problem for ...

Solving Linear Diophantine Equations and Linear Congruential

THE CONGRUENT NUMBER PROBLEM 1. Introduction A right

search for congruent numbers the “principal object of the theory of rational right triangles. Assume there is a solution to (2.1) in positive integers.

Puzzle Type Examples of Linear Congruence

Aug 29 2018 Keywords: Diophantine equation; linear congruence; incongruent solutions; puzzle. 1. INTRODUCTION. Number Theory sometimes called Higher ...

3 Congruence - New York University

Theorem 3 10Ifgcd(a;n)=1 then the congruence ax bmodn has a solution x=c In this case the general solution of the congruence is given by x cmodn Proof: Sinceaandnare relative prime we can express 1 as a linear combination of them: ar+ns=1 Multiply this bybto getabr+nbs=b Takethismodnto get abr+nbs bmodnorabr bmodn

Section 48 Key Terms Review Questions and Problems

Example: Solve the congruencex2 9 (mod 16) Since 16 = 24 we nd the solutions mod 2 then work upward It is easy to see that there is a unique solution tox2 9(mod 2) namelyx 1 (mod 2) Next we lift to nd the solutions modulo 22: any solutionmust be of the formx= 1 + 2k so we get (1 + 2k)2 9(mod 22) which simpli es to 1 9 (mod 22)

The Congruent Number Problem - UNCG

number if it is the area of a right triangle with rational length sides The Congruent Number Problem is to nd an algorithm to determine whether a given natural number is congruent or not There is a conjectural solution but a proof would require solving a millennium problem worth a million dollars concerning elliptic curves The goal of this

Linear Congruences

Then the congruence ax b (mod m) has no solutions iff d -b In case djb the congruence has exactly d solutions that are pairwise incongruent modulo m Proof First note that djax for all x 2Z “( ” If d -b then d -ax b for all x 2Z Because m is a multiple of d this implies that m-ax b for all x 2Z That is

Problems in Elementary Number Theory

PROBLEMS IN ELEMENTARY NUMBER THEORY Version 0 61 : May 2003 1 Introduction The heart of Mathematics is its problems Paul Halmos 1 Aim of This Book The purpose of this book is to present a collection of interesting questions in Elementary Number Theory This resource book was written for the beginners in Number Theory

Searches related to number theory congruence problems and solutions filetype:pdf

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 (see Q 7 below) to ?nd the reciprocal a? ? F× p of a ? F

[PDF] 3 Congruences and Congruence Equations

3 Congruences and Congruence Equations A great many problems in number theory rely only on remainders when dividing by an integer Recall

[PDF] 3 Congruence

Quantitative Reasoning: Computers Number Theory and Cryptography 3 Congruence Congruences are an important and useful tool for the study of divisibility

[PDF] Number Theory Problem Sheet 2 SOLUTION Solving Linear

Mathematics 4: Number Theory Problem Sheet 2 SOLUTION Solving Linear congruences and linear equations in integers Before solving higher degree equations

[PDF] Congruences in number theory - CORE

The results of these two theorems can be expressed by the following recursive formulae: Case I (Theorem I) Let A^ be a solution of the congruence x n = a

[PDF] SOLUTIONS TO PROBLEM SET 1 Section 13 Exercise 4 We see

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

[PDF] Number theory - The Open University

Regrettably mathematical and statistical content in PDF files is unlikely to be Number theory is a branch of mathematics concerned with properties of

[PDF] 250 PROBLEMS IN ELEMENTARY NUMBER THEORY

"250 Problems in Elementary Number Theory" presents problems and their solutions in five specific areas of this branch of mathe-

[PDF] linear-congruencespdf

I need to show that of these infinitely many solutions there are exactly d distinct solutions mod m Suppose two solutions of this form are congruent mod m: x0

[PDF] Congruence problems and questions regarding sequences - ICMAT

Theory Elementary Number Theory and the so called Additive Combinatorics The presented manuscript is divided into two different parts: congruence problems

[PDF] Dr Zs Number Theory Lecture 10 Handout: Linear Congruences

Dr Z 's Number Theory Lecture 10 Handout: Linear Congruences and Modular Problem 10 1: Without actually solving find out how many solutions there are

What is congruence in number theory?

Some texts on number theory use this latter relationship as the definition of congruence: Two integers a and b are said to be congruent modulo n, if n | ( a b ). Using this latter definition as the starting point, prove that if ( a mod n) = ( b mod n ), then n divides ( a b ).

What is the proof of congruence?

The proof begins by justifying that ¯¯¯¯¯¯¯¯AC ?¯¯¯¯¯¯¯¯CB A C ¯ ? C B ¯, which shows that those two sides are congruent. Also, we know from the given statement that the other two corresponding pairs of sides are congruent.

Why is it difficult to choose a congruence test?

When proving results involving similarity and congruence, some students may still find it challenging to decide which test to use. Problems involving equality of lengths usually involve congruence. Problems involving proportions involve similarity. In selecting a congruence test, students may make these errors:

What are the basic properties of a congruence relation?

Basic properties[edit] The congruence relation satisfies all the conditions of an equivalence relation: Reflexivity: a? a(mod n) Symmetry: a? b(mod n)if b? a(mod n). Transitivity: If a? b(mod n)and b? c(mod n), then a? c(mod n) If a1? b1(mod n)and a2? b2(mod n),or if a? b(mod n),then:

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] Mathematics 4: Number Theory Problem Sheet 2 SOLUTION