Fundamental Problems in Number Theory.pptx

I am Marvin Jones, a Number Theory Homework Expert at mathsassignmenthelp.com. I hold a Master's in Mathematics from Columbia University, and have been assisting students with their homework for the past six years. I specialize in number theory assignments.
For any number theory assignment solution or homework help, visit mathsassignmenthelp.com, email [email protected], or call [phone]. This sample assignment solution is a prove of our work.

1. Fundamental Problems in Number Theory: Well-Ordering, Linear Combinations, and Divisibility For any help regarding number theory Visit: https://www.mathsassignmenthelp.com/number-theory / E-mail: [email protected] or Call us at : [phone] Maths Assignment Help

2. Introducing an exemplary assignment from www.mathsassignmenthelp.com , where students find comprehensive solutions to mathematical problems. This sample task delves into various mathematical concepts, offering clear explanations and solutions. From proving the existence of certain integers to utilizing the Euclidean algorithm, each question provides a challenging yet insightful exploration of fundamental mathematical principles. Through detailed solutions and step-by-step reasoning, students can grasp key concepts more effectively. In particular, the assignment addresses topics such as integer divisibility, linear combinations, and the Euclidean algorithm's efficiency. As students navigate through these questions, they not only enhance their problem-solving skills but also deepen their understanding of mathematical theory. This assignment exemplifies the dedication to excellence and academic support offered by www.mathsassignmenthelp.com , empowering students to excel in their mathematical endeavors . Maths Assignment Help

3. Q. 1 . Let a>0andb be integers. Show that there is an integer k such that b+ka > 0. (Hint: use well-ordering.) Sol. Suppose not. Then let S be the set of integers , so by hypothesis S consists entirely of nonnegative integers. By the Well – Ordering Principle, it has a smallest positive element, say, b+ka . But then b+(k-1)a is smaller since a>0, contradiction. Q.2 Let a and b be positive integers whose gcd is 1. Find the largest positive integer n(a, b)which is not a non-negative integer linear combination of a and b. Prove your answer (i.e. show that n(a, b) cannot be represented as ax + by with x, y ∈N ∪{0} and that every greater integer can be represented in such a way ). Sol. Maths Assignment Help

4. The largest such integer is ab − a − b . To see it’s not a nonnegative integer linear combination, suppose ab − a − b = ax + by with x, y ∈ Z ≥ . Then a ( b − 1 − x ) = b ( y + 1) . And since ( a, b ) = 1 we have a | y + 1 (and b | b − 1 − x ). This forces y ≥ a − 1 because y + 1 ≥ 1. So ax + by ≥ a · 0 + b ( a − 1) = ab − b > ab − a − b Q.3 Let a > 1 be a positive integer, and m, n be natural numbers. Show that a m − 1| a n − 1 if and only if m | n . Show that the gcd of a m − 1 and a n − 1 is a ( m,n ) − 1. Sol. One direction is clear: if m | n then n = mk for some positive integer k , and Maths Assignment Help

5. a n − 1 = a mk − 1 = ( a m − 1)( a m ( k− 1) + a m ( k− 2) + · · · + a m + 1) is divisible by a m − 1. Now if m ‡ n , we write n = mk + r with 0 < r < m . Then a n − 1 = a mk + r − 1 = a mk + r − a r + a r − 1 = a r ( a mk − 1) + a r − 1 . Now a m − 1 divides a mk − 1 but it doesn’t divide a r − 1, since 0 < a r − 1 < a m − 1. So a m − 1 can’t divide a n − 1. Q.4 Use the Euclidean algorithm to find an integer solution ( x , y ) to 89 x + 43 y = 1. Then use your solution to describe all possible integer solutions systematically. Sol. Using the Euclidean algorithm:   Maths Assignment Help

6. Using the Euclidean algorithm:   89 1 0 2 43 0 1 14 3 1 − 2 1 − 14 29 So (−14)89 + (29)43 = 1 , i.e., ( x , y ) = (−14 , 29). Now if x, y is any solution then 89( x − x ) + 43( y − y ) = 0 . And since 43 and 89 are coprime , 43| x − x and 89| y − y . Then we have   x = x − 43 k y = y + 89 k for some k ∈ Z . It’s easy to verify that all solutions of this form satisfy 89 x + 43 y = 1 . So all the solutions are given by ( x, y ) ∈ {(−14 − 43 k, 29 + 89 k ) : k ∈ Z} Maths Assignment Help

7. Q.5 Let 1 < a < b be integers. Show that the number of division steps involved in the Euclidean algorithm to compute the gcd of a and b is at most a (universal) constant times log( a ). (Hint: observe what happens after two steps of the algorithm). Sol. Since 1 < a < b , b = aq + r < r < a a = rq ′ + s 0 ≤ s < r (If r = 0 we’re done in one step.) So after two steps, ( a, b ) gets replaced by ( s, r ). We claim s < a/ 2 . If in step 1, r ≤ a/ 2, then we’re done by s < r. Otherwise, r > a/ 2 and in step 2 we’ll have q ′ = 1 and s = a − r < a/ 2 . In any case, we see that after two steps, the value of a at least halves. So after at most 2 log2 a steps, we’ll get a pair ( a new , b new ) such that a new < 2 , i.e., a new = 1. Therefore the algorithm terminates after at most C log a steps for C = 2 / log 2 . Maths Assignment Help

8. Q.6 This will be your first exercise using the math software gp /PARI, which specializes in number theory calculations (see the class website for instructions on how to download it, and links to tutorials). Using gp , tabulate the number of primes less than x, for x = 10000, 20000,... , 100000. Also tabulate the number of primes less than x and of the form 4k + 1, and the number of the form 4k + 3, and finally, tabulate x/ log(x) (natural logarithm). Turn in a printout of your code. What are your observations ? Sol. You should notice that about 50% of the primes are 1 mod 4 and about 50% are 3 mod 4. Also, the number of primes which are 3 mod 4 seems to be larger than the number of primes 1 mod 4, up to any integer. This is not always the case—see the article “Prime number races” by Andrew Gronville and Greg Martin for a fascinating account . Maths Assignment Help

9. Q.7 A board has squares numbered 1 through n . Two players A and B play the following game: A starts, putting a token on some square a 1 . Then B puts a token on some square b 1 , which is not allowed to divide a 1 . Then A follows with a 2 , such that a 2 t a 1 and a 2 t b 1 , and so on (at any stage, the number of the square selected must not divide any of the previous ones). The last person to put down a token wins. Try playing this game for n = 10 , 12 , 24. Who wins? Prove your observation for general n . Bonus: Can you find a winning strategy? Sol. A can always win. Proof : Note that for any fixed n , there are only finitely many squares on the board, so it’s a finite game, which means that one of the players must have a winning strategy. If B has a winning strategy, we’ll show a contradiction. Since A puts down the first token, A can choose to put it down on the square 1. Then B must have a winning strategy from here, so suppose B puts down a token on square Maths Assignment Help

10. k . However, A could start with k instead, and imitate what B would have done ( B can’t use 1, since 1 divides k ). This shows that A wins if starting with k , contradiction . Note: I don’t know of an explicit winning strategy; that problem seems to be unsolved ! Q.8 Show that there are infinitely many primes of the form 4 k + 3 . Sol. We use proof by contradiction, as in Euclid’s proof. Suppose there are only finitely many primes of the form 4 k + 3, say, p 1 , . . . , p n . Now consider N = 4 p 1 · · · p n − 1 . Clearly N > 1, and N ≡ 3 mod 4 . So N must have a prime divisor congruent to 3 mod 4, else if all the factors of N are congruent to 1 mod 4 then N ≡ 1 (mod 4). But then some p i must divide N , a contradiction since p i |4 p 1 · · · p n and p i / | 1 . Maths Assignment Help

11. Q.9 Solve the congruence x 3 − 9 x 2 + 23 x − 15 ≡ 0 (mod 143 ). Sol. It’s enough to solve the congruence mod 11 and mod 13, and then combine the solutions by Chinese Remainder Theorem. Now x 3 9 x 2 + 23 x 15 factors as ( x 1)( x 3)( x 5), so solutions mod 11 or mod 13 are 1 , 3 , 5 in each case . To combine, we first need x, y such that 13 x + 11 y = 1. For instance x = 5 , y = 6 works. (We can find x, y by Euclidean algorithm). So if we have a solution a mod 11 and a solution b mod 13 then the Chinese Remainder Theorem recipe tells us that ( −5)(13) a + (6)(11) b = −65 a + 66 b is a solution mod 143. Running this over a ∈ 1 , 3 , 5 and b ∈ 1 , 3 , 5 we get 9 solutions: 1, 3, 5, 14 , 16, 27, 122, 133, 135 Maths Assignment Help

12. Q.10 What are the last two digits of 2 100 and of 3 100 ? Sol. We just need to compute these expressions mod 4 and mod 25, and then combine using CRT. Note that (1)(25) + (−6)(4) = 1 , so if x ≡ a mod 4 and x ≡ b mod 25 then x ≡ 25 a − 24 b (mod 100 ) . For 2 100 : We have 2 100 ≡ 0 (mod 4) and 2 100 = 2 5 φ (25) ≡ 1 (mod 25) . So the last two digits are 25 · 0 − 24 · 1 ≡ 76 . For 3 100 : We have 3 100 = 3 50 φ (4) ≡ 1 (mod 4) and 3 100 = 3 5 φ (25) ≡ 1 (mod 25) . So the last two digits are 25 · 1 − 24 · 1 ≡ 01 . Maths Assignment Help

13. Q.11 Show that the number n = 561 = 3 · 11 · 17 satisfies the property P : for any a coprime to n , we have a n −1 ≡ 1 (mod n ). Let n be a squarefree composite number satisfying P . Show that n has at least 3 prime factors. Write down a sufficient condition for n = pqr (where p, q, r are primes) to satisfy property P . Then write a gp program to generate a list of ten such numbers n . Sol. We need to show that a 560 ≡ 1 mod 3, mod 11, and mod 17 for any a coprime to 561. Since a is coprime to 3, a 2 ≡ 1 (mod 3) , so a 560 = a 2 · 280 ≡ 1 (mod 3) . Since a is coprime to 11, a 10 ≡ 1 (mod 11) , so a 560 = a 56 · 10 ≡ 1 (mod 11) . Since a is coprime to 17, a 16 ≡ 1 (mod 17) , so a 560 = a 35 · 16 ≡ 1 (mod 17 ) Maths Assignment Help

14. b) Suppose n = pq with p, q distinct primes satisfies property P . Then for all a coprime to p and q , we have a pq− 1 ≡ 1 (mod p ) and a pq− 1 ≡ 1 (mod q ) . Assume, without loss of generality, that p < q. Then apq− 1 = a ( q− 1) p + p− 1 = a ( q− 1) p · ap− 1 ≡ 1 p · a p− 1 (mod q ) . Now for any x coprime to q, we can let a be the unique integer mod pq which satisfies a x (mod q) and a 1 (mod p), so that a is coprime to pq and thus xp−1 1 (mod q). However , because of the existence of a primitive root mod q, we know that q 1 is the smallest positive integer such that xq−1 1 (mod q) for every x coprime to q. Since p 1 < q 1, we have a contradiction. c) A sufficient condition is that p −1| pqr −1. This implies that qr ≡ 1 (mod p −1) , pr ≡ 1 (mod q −1) Maths Assignment Help

15. and pq ≡ 1 (mod r − 1) . Using it to search we find the following numbers : 561 = 3 · 11 · 17 1105 = 5 · 13 · 17 1729 = 7 · 13 · 19 2465 = 5 · 17 · 29 2821 = 7 · 13 · 31 6601 = 7 · 23 · 41 8911 = 7 · 19 · 67 10585 = 5 · 29 · 73 15841 = 7 · 31 · 73 29341 = 13 · 37 · 61 . Q.12 Do there exist arbitrarily long sequences of consecutive integers, none of which are squarefree ? (i.e. given any positive integer N , does there exist a sequence of integers x, x +1 ,..., x + N −1 such that none of these is squarefree ?) Prove your assertion . Maths Assignment Help

16. Sol. Yes. Pick distinct primes p 1 , . . . , p N and let x solve x ≡ 0 (mod p 2 ) x + 1 ≡ 0 (mod p 2 ) x + N − 1 ≡ 0 (mod p 2 ) This has solutions mod p 2 · · · p 2 , by CRT. We can pick x positive. Then for each i , x + i − 1 is divisible by p 2 , and thus is not square free. Q.13 This computational exercise will involve the notion of “density”. We say that a set S of primes has density δ if the limit   Maths Assignment Help

17. exists and equals δ . Let f ( x ) = x 3 − 2. Write a gp program to calculate the set S of primes p less than 10000 such that f has a solution modulo p . Make a conjecture about the density of such primes . Now do the same exercise for f ( x ) = x 3 − 3 x − 1. (Bonus) What qualitative feature of f differentiates these two cases? Sol. You should find that the density is about 2/3. You should find that the density is about 1/3 . The key difference is the Galois group, which is S 3 for (a) and Z / 3Z for (b). Maths Assignment Help

18. The reason for the distribution you see is a deep theorem in algebraic number theory called the Chebotarev density theorem. In terms of group theory, the main difference is that the number of permutations in S 3 with a fixed point is 4, leading to the fraction 4 / 6 = 2 / 3 , while the corresponding number for A 3 = {(1) , (123) , (132)} is 1, leading to the fraction 1 / 3 . To get more such types of problems or solution to any assignment, Feel free to visit: https://www.mathsassignmenthelp.com/ or call at [phone] . Maths Assignment Help