Monic irreducible polynomials P64196


Statement
 

pdf   zip

thehtml

Here, we consider polynomials in Fp[x], that is, polynomials on x whose coefficients are elements of Fp={0, 1, 2, …, p−1}, where p is a prime number.

A polynomial is monic if the coefficient of its term with largest degree is 1. A polynomial is irreducible if it cannot be written as the product of two polynomials of smaller degree. Your task is to count the number of monic, irreducible polynomials of Fp[x] of a given degree d.

Too difficult? Do not despair! The problem is not so hard, once you know that, in Fp[x], every monic polynomial can be written in a unique way as a factor of monic, irreducible polynomials. For instance, in F2[x] there are 4 monic polynomials of degree 2 (in F2[x], all polynomials are monic), but only one of them is irreducible:

x2 = x· x             ⁠ ⁠ x2+1 = (x+1)·(x+1)    ⁠ ⁠ x2+x = x· (x+1)       ⁠ ⁠ x2+x+1 = ⁠ ⁠ ???

In F2[x], there are 8 monic polynomials of degree 3, but only two of them are irreducible:

     
x3= x· x · x                  ⁠ ⁠   ⁠ ⁠ x3 + x2= x· x· (x+1)                
x3+1= (x+1)·(x2+x+1)             ⁠ ⁠   ⁠ ⁠ x3+x2+1= ⁠ ⁠ ???                       
x3 + x= x· (x+1)· (x+1)       ⁠ ⁠   ⁠ ⁠ x3 + x2 + x= x· (x2+x+1)               
x3+x+1= ⁠ ⁠ ???                  ⁠ ⁠   ⁠ ⁠ x3+x2+x+1= (x+1)·(x+1)·(x+1)        

Input

Input consists of several cases, each with a prime number 2 ≤ p ≤ 30 and an integer number 2 ≤ d ≤ 30. Additionally, we have pd < 109.

Output

For every case, print the number of monic, irreducible polynomials in Fp[x] of degree d.

Public test cases

  • Input

    2 2
2 3
2 4
2 30
3 2
3 3
3 4
3 19
29 6

    Output

    1
2
3
35790267
3
8
18
61171656
99133020
    • Information
    Author
    Omer Giménez
    Language
    English
    Official solutions
    C++
    User solutions
    C++