代做Math 3527 Number Theory 1, Spring 2024 Homework 7调试Haskell程序

日期：2024-03-17 04:42

Math 3527 Number Theory 1, Spring 2024

Homework 7

Due Tue Mar 19th.

Part I: No justi cations are required for these problems. Answers will be graded on correctness.

1. Factor the given integers using the stated procedure (make sure to give enough detail so the computations can be followed):

(a) N = 1084055561 by looking for a Fermat factorization.

(b) N = 5686741440097 by looking for a Fermat factorization.

(c) N = 1032899106233 by using Pollard's (p - 1)-algorithm with a = 2.

(d) N = 12038459 by using Pollard's (p - 1)-algorithm with a = 2.

(e) N = 1626641013131 by using Pollard's ρ-algorithm with a = 2 and p(x) = x2  + 1. (f) N = 12038459 by using Pollard's ρ-algorithm with a = 2 and p(x) = x2  + 1.

2. For each element in each ring Z[pD], determine (i) whether it is a unit and if so ndits multiplicative inverse, and (ii) whether it is irreducible and if not  nd a nontrivial factorization. (a) The elements -i, 3 + 2i, 1 + i, and 1 + 5i in Z[i]. (b) The elements 1 + 2p5, 9 + 4p5 , 5 +p5, 21 + 4p5 in Z[p5] .

3. Use the Euclidean algorithm in each Euclidean domain to compute a greatest common divisor of each pair of elements, and then to write it as a linear combination of the elements: (a) The polynomials x6 - 1 and x8 - 1 in R[x]. (b) The elements 11 + 27i and -9 + 7i in Z[i]. (c) The polynomials x3 + x2 + 1 and x4 + x in R[x]. (d) The elements 43 - i and 50 - 50i in Z[i]. (e) The elements x4 + 2x + 1 and x3 + x in F3 [x]. (f) The elements 9 + 43i and 22 + 10i in Z[i].

4. As proven on homework 2, the only possible primes of the forman - 1 are the Mersenne numbers 2p - 1 where p is a prime. The goal of this problem is to study the prime factorizations of Mersenne numbers. (a) Apply the Miller-Rabin test with a = 2, 3, 5 on 2p - 1 for p = 11, 13, 17, 19, 23, 29. You should  nd that three values are composite: why can you not conclude that the other three values are necessarily prime? (b) Use Pollard's ρ-algorithm with a = 3 and polynomial p(x) = x2 + 1 to  nd the factorizations of the three values 2p - 1 you identitied as composite in part (a). (Note that the largest one has three prime factors;make sure to  nd all three by extending the computation past where the  rst prime factor is found.) How many steps are required to nd the factorizations?

Part II: Solve the following problems. Justify all answers with rigorous, clear explanations.

5.  For all of the factorizations in problem 4, notice that all of the prime factors of 2p  - 1 are congruent to 1 modulo p. The goal is now to prove this fact, which was   rst established by Euler.

(a)  Suppose that q is a prime that divides 2p - 1.  Show that the order of 2 modulo q must equal p. (b)  Suppose that q is a prime that divides 2p - 1. Show that q = 1 (mod p).

6.  The goal of this problem is to prove that the ring R = Z[p-2] is a Euclidean domain under its norm function N (a + bp-2) = a2  + 2b2  using a similar argument to the one used to show Z[i] is Euclidean.

(a)  Suppose that c + dp-2 is not zero. Write  c(a)  d(b)p(p) --2(2) in the form x + yp-2 for rational numbers x and

y. [Hint: Rationalize the denominator.]

(b) With notation from part  (a), let s be the closest integer to x and t be the closest integer to y.   Set q = s + tp-2 and r = (a + bp-2) - (s + tp-2)(c + dp-2). Prove that N (r) N (c + dp-2).

(c)  Deduce that R is a Euclidean domain.

(d)  Use the Euclidean algorithm in R to   nd the greatest common divisor of 33 + 5p-2 and 8 + 11p-2 in R, and then write the gcd as a linear combination of these elements.

Remark:  By a similar argument, one may show that Z[p2] and Z[p3] are also Euclidean domains.