Scribd Logo
Upload

Welcome to Scribd!

  • 52 views

    430 Pset 3 Solutions

    Uploaded by

    Gag Paf
    This document contains the problems and solutions for Problem Set 3 of an introductory number theory course. It includes 5 problems: 1. Showing that the only solutions to x^2 ≡ 1 (mod p^n) are x ≡ 1 or -1 (mod p^n) for an odd prime p. 2. Finding the unique solution to a system of congruences modulo 84 using the Chinese Remainder Theorem. 3. Finding the 6 solutions to a cubic congruence modulo 45 by applying the Chinese Remainder Theorem and Hensel's lemma. 4. Showing that an equation has no solutions modulo 9 and thus no solutions modulo 3^4. 5

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    430 Pset 3 Solutions

    Uploaded by

    Gag Paf
    52 views2 pages
    This document contains the problems and solutions for Problem Set 3 of an introductory number theory course. It includes 5 problems: 1. Showing that the only solutions to x^2 ≡ 1 (mod p^n) are x ≡ 1 or -1 (mod p^n) for an odd prime p. 2. Finding the unique solution to a system of congruences modulo 84 using the Chinese Remainder Theorem. 3. Finding the 6 solutions to a cubic congruence modulo 45 by applying the Chinese Remainder Theorem and Hensel's lemma. 4. Showing that an equation has no solutions modulo 9 and thus no solutions modulo 3^4. 5

    Original Description:

    number theory

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains the problems and solutions for Problem Set 3 of an introductory number theory course. It includes 5 problems: 1. Showing that the only solutions to x^2 ≡ 1 (mod p^n) are x ≡ 1 or -1 (mod p^n) for an odd prime p. 2. Finding the unique solution to a system of congruences modulo 84 using the Chinese Remainder Theorem. 3. Finding the 6 solutions to a cubic congruence modulo 45 by applying the Chinese Remainder Theorem and Hensel's lemma. 4. Showing that an equation has no solutions modulo 9 and thus no solutions modulo 3^4. 5

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    52 views2 pages

    430 Pset 3 Solutions

    Uploaded by

    Gag Paf
    This document contains the problems and solutions for Problem Set 3 of an introductory number theory course. It includes 5 problems: 1. Showing that the only solutions to x^2 ≡ 1 (mod p^n) are x ≡ 1 or -1 (mod p^n) for an odd prime p. 2. Finding the unique solution to a system of congruences modulo 84 using the Chinese Remainder Theorem. 3. Finding the 6 solutions to a cubic congruence modulo 45 by applying the Chinese Remainder Theorem and Hensel's lemma. 4. Showing that an equation has no solutions modulo 9 and thus no solutions modulo 3^4. 5

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    MT 430 Intro to Number Theory

    PROBLEM SET 3

    Due Thursday 2/14


    Remark. Here, as in class, whenever working modulo m, we use notation x to
    denote a multiplicative inverse of x modulo m. Whenever (x, m) = 1, x is the
    unique residue modulo m such that xx 1 (mod m).
    Problem 1. Let p be an odd prime number. Show that the congruence
    x2 1 (mod pn )
    has only the two solutions x 1 (mod pn ) and x 1 (mod pn ).
    Solution: The statement x2 1 (mod pn ) is equivalent to
    pn | (x2 1) = (x 1)(x + 1).
    Since (x + 1) (x 1) = 2, the numbers (x + 1) and (x 1) cannot be divisible
    by p simultaneously. If (x 1) is not divisible by p, then since p is a prime and pn
    divides the product (x 1)(x + 1), we must have pn | x + 1. Similarly, if (x + 1) is
    not divisible by p, we must have pn | x 1. 
    Problem 2. Find all x such that

    x 1 (mod 4)

    x 2 (mod 3)

    x 5 (mod 7)

    We apply the algorithmic version of Chinese Remainder Theorem from class. Take
    b1 = 21 = 1 = 1 (mod 4), b2 = 28 = 1 = 1 (mod 3), and b3 = 12 = 5 = 3 (mod 7).
    Then
    x = 1 b1 21 + 2 b2 28 + 5 b3 12 = 21 + 56 + 180 5 (mod 84)
    is the unique solution of the system modulo 84 = 4 3 7.
    Problem 3. Solve the congruence x3 + 2x 3 0 (mod 45).
    Solution: Note that 45 = 5 32 . First, we solve separately the congruence x3 +
    2x 3 0 modulo 5 and modulo 32 . The solutions of x3 + 2x 3 0 (mod 5) are
    x 1, 3 (mod 5).
    To find solutions modulo 32 , we first observe that modulo 3, x3 +2x3 x+2x
    3 3x 3 0 (mod 3) by Fermats little theorem. Hence all x 0, 1, 2 (mod 3)
    are all solutions modulo 3. We then compute that (x3 + 2x 3)0 = 3x2 + 2 2
    (mod 3). Hence by Hensels lemma, every solution modulo 3 lifts to a unique
    solution modulo 9. Since 2 = 2 (mod 3), we see that
    x 0 (mod 3) lifts to x 0 2f (0) = 0 2(3) = 6 (mod 9)
    x 1 (mod 3) lifts to x 1 2f (1) = 1 0 = 1 (mod 9)
    x 2 (mod 3) lifts to x 2 2f (2) = 2 18 = 2 (mod 9)
    We summarize that solutions of x3 + 2x 3 0 (mod 9) are x 1, 2, 6 (mod 9).
    Combining these with the solution x 1, 3 (mod 5) of x3 + 2x 3 0 (mod 5)
    and applying Chinese Remainder Theorem, we obtain 6 solutions modulo 45:
    x 1, 28, 11, 38, 6, 33 (mod 45).
    1
    2 PROBLEM SET 3

    
    Problem 4. Solve x5 + x4 + 1 0 (mod 34 ).
    Hint: Hensels lemma is inapplicable here because f 0 (1) = 3 0 (mod 3). You
    can still use the unique solution modulo 3 to look for solutions modulo 9.
    Solution: The only solution of x5 + x4 + 1 0 (mod 3) is x = 1. Hence the only
    candidates for solutions of x5 + x4 + 1 0 (mod 32 ) are x = 1, 1 + 3 = 4, and
    x = 1 + 6 = 7. We check that
    15 + 14 + 1 3 (mod 9)
    5 4
    4 + 4 + 1 3 (mod 9)
    75 + 74 + 1 3 (mod 9)
    5 4
    Therefore, the x + x + 1 0 has no solutions modulo 9 and thus no solutions
    modulo 34 . 
    Problem 5 (Edited on 2/12). Let p be an odd prime and suppose that a is an
    integer such that x2 a (mod p) has a solution and a 6 0 (mod p). Show that
    x2 a (mod pn ) has a solution for all integers n 1.
    Solution: The proof is by induction. The base case of n = 1 is given to us. Suppose
    b is a solution of x2 a 0 (mod pn ). Since (x2 a)0 = 2x and 2b 6 0 (mod p),
    Hensels lemma says that b lifts to a solution of x2 a 0 (mod pn+1 ). 
    Remark. Eulers criterion says that for a 6 0 (mod p) the equation x2 a
    (mod p) has a solution if and only if
    p1
    x 2 1 (mod p).
    Assuming Eulers criterion, the old statement of Problem 5 is equivalent to the new
    statement.

    You might also like