Scribd
Upload
7 views2 pages

Homework 07

This document is an exercise sheet for a Number Theory and Cryptography course, detailing various mathematical problems related to polynomial division and congruences. It includes exercises on proving divisibility, solving systems of congruences, computing polynomial quotients and remainders, and finding real solutions to polynomial equations. Each exercise is assigned a specific point value, indicating its difficulty or importance.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Homework 07

This document is an exercise sheet for a Number Theory and Cryptography course, detailing various mathematical problems related to polynomial division and congruences. It includes exercises on proving divisibility, solving systems of congruences, computing polynomial quotients and remainders, and finding real solutions to polynomial equations. Each exercise is assigned a specific point value, indicating its difficulty or importance.

Uploaded by

José Castro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Number Theory and Cryptography

Math UN3020
New York, 2023/03/01

Exercise Sheet 7

Polynomial division

Exercise 1 (8 points). Prove that, for all n ∈ N,

5 | (n5 − n) .

(Hint:) you may try by induction.

Exercise 2 (9 points). Solve the following systems of congruences.

(a) (
x≡6 (mod 10)
x ≡ 11 (mod 15)

(b) (
x≡3 (mod 21)
x ≡ 11 (mod 14)

(c) 
x ≡ 10
 (mod 12)
x ≡ 16 (mod 18)

x ≡ 10 (mod 15)

Exercise 3 (9 points). Compute the quotient and remainder of the polynomial division between
the following pairs of polynomials in Q[x].

(a) 2x4 − 1, x2 − 2x + 1.

(b) 6x4 + 3x2 − 3, 2x3 + 1.

(c) 3x4 , x − 1.

1
Exercise 4 (9 points). Compute the quotient and remainder of the polynomial division between
the following pairs of polynomials in Z13 [x].

(a) [2]x4 − [1], [3]x2 − [2]x + [1].

(b) [6]x4 + [3]x2 − [3], [5]x3 + [1].

(c) [3]x4 , [2]x − [1].

Exercise 5 (8 points). Prove that, for every n ≥ 1, the numbers n4 + 3n2 + 1 and n3 + 2n are
coprime.

Exercise 6 (8 points). Let p(x) be a polynomial with integer coefficients

p(x) = an xn + · · · + a0 ,

where ai ∈ Z and an 6= 0. Let st ∈ Q be a rational root of p(x), where we assume that


gcd(s, t) = 1. Prove that s, t satisfy the following condition:

s | a0 AND t | an .

(Hint:) Write explicitly the condition p( st ) = 0. Multiply it by tn .

Exercise 7 (9 points). Find all the real solutions to the following equations.

(a) x3 − 6x2 + 9x − 2 = 0.

(b) 3x4 − x3 − 6x + 2 = 0.

(c) 2x5 + x4 − 8x3 − 4x2 + 8x + 4 = 0.

(Hint:) First, find one rational solution, by try-and-error. Exercise 6 restricts the search.

You might also like