Factorizations of numbers of shape (k^2·41)^41 - 1

Last update

Notes

(k^2·41)^41 - 1 with k ≤ 1000

Let z := k^2·41 and N := z^41 - 1,
let C := z^20 + 21z^19 + 67z^18 + 49z^17 + 7z^16 + 35z^15 + 15z^14 + 11z^13 - 23z^12 - 65z^11 - 31z^10 - 65z^9 - 23z^8 + 11z^7 + 15z^6 + 35z^5 + 7z^4 + 49z^3 + 67z^2 + 21z + 1
and D :=          z^19 +  7z^18 + 11z^17 + 3z^16 +  3z^15 +  5z^14 +   z^13 +   z^12 -  9z^11 -  7z^10 -  7z^9 -  9z^8 +   z^7 +   z^6 +  5z^5 + 3z^4 +  3z^3 + 11z^2 +  7z + 1,
let L := C - 41kD and M := C + 41kD.
Then we have the factorization N = (z-1)LM, which is of type Aurifeuillian.

This is a special case of Lucas' formulas for cyclotomic polynomials.
The above polynomials C and D are taken from Hans Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser, 1994, p. 444.

Many values of k admit very simple factorizations of the corresponding numbers L and M.
To set an example, let k = 999996009. Then we have
L/83 = 2170349675056433298278784851656592752032507260604123523370271162869244188256986740393449026534226086629748681406974092314596786168308026638110899250066420598073696207881906640052259562391791689884987629414823072613585156068080071474715359722093871001576534508000974928773539839942915231852443611534973598810102533556780068483229792645166823157628433093520947978331737666396143456238107002319, which is a 391-digit prime and
  M  = 180139023389963448052208375995132093958360983055595001275451883694571162007523088158239814503153027537803272544011200032091310901996593169127011724151107729762158425487156762766346323495712029355819717254088604287071949855238390401000934427884933322433767085360478312969531864266147312409514045247991372803299730167558826570159093560246287009152885821260309133615005865962990954988547789591133, which is a 393-digit prime.

Contributors

Factorizations