mod 6

[Don Reble]

> a(n) is the largest prime factor of a(n-1)^2-a(n-1)+1 :
> 2,3,7,43,139,19183,2766679,...

  ..., 7654509922363, 12024175458769, 19613203998120151, 28481478194359,
  811194600135718721501226523, 27611803483012345815884796289

> It seems that the same law as A056650 exists.
> "Except the first term all terms are 1 mod 6."
>
> I don't have any idea to prove this proposition.
> Is it possible to prove it?


There's a more general theorem:

    If N is an integer, then N^2-N+1 is not divisible by any prime
    of the form 6k+5.

The statement is similar to Legendre's theorem for factors of a^n+-b^n,
and the proof resembles his proof.

Definitions:

    Let C1(n) = n-1,
        C2(n) = n+1,
        C3(n) = n^2+n+1,
        C6(n) = n^2-n+1.
    So that C1(n)*C2(n)*C3(n)*C6(n) = n^6-1.

    And let C123(n) = C1(n)*C2(n)*C3(n).

        (You might recognize the cyclotomic polynomials. C6 is the
         polynomial mentioned in the theorem statement.)

Proof:

Let P be a 6k+5 prime,
    N be an integer, and
    X be the largest integer such that P^X divides N^6-1.

If X = 0:

    then P does not divide N^6-1, and so can't divide a factor of
    N^6-1, especially C6(N).

If X > 0:

    P does divide N^6-1, and so cannot divide N^6 nor N. N is therefore
    a member of P^X's multiplicative group. Let the R be the order of N
    in that group: that is, the least positive integer R such that
    N^R = 1 mod P^X.

    Since N^6 = 1 mod P^X, R divides 6. R is 1, 2, 3, or 6.

    R divides the order of the group, P^(K-1)*(P-1). Now, P is a 6k+5
    prime: it is at least 5, and so is not divisible by any prime factor
    of R. Therefore R divides P-1, and P = R*F+1, for some F.

    If R=6, then P=6F+1: contradiction! Therefore R is 1, 2, or 3.

    Since N^R = 1 mod P^X, then P^X divides N^R-1.
    So P^X divides one of N^1-1, N^2-1, or N^3-1; that is
       P^X divides one of C1(N), C1(N)*C2(N), or C1(N)*C3(N).
    Therefore P^X divides C123(N). Let C123(N)=Q*P^X.

    P^(X+1) does not divide N^6-1, so P does not divide (N^6-1)/P^X.
    Therefore P does not divide (N^6-1)/(Q*P^X) = C6(N).

Either way, P does not divide C6(N) = N^2-N+1. QED.

----

And I have two more generalizations (sigh).

C6(N+1) = C3(N).
So if a prime can't divide any C6(N+1), neither can it divide any C3(N).

    If N is an integer, then neither N^2-N+1 nor N^2+N+1 is divisible by
    any prime of the form 6k+5.

Also, each positive 6k+5 number is divisible by a 6k+5 prime. (Because it
isn't divisible by 2 nor 3, and the 6k+1's are closed under
multiplication mod 6.) So:

    If N is an integer, then neither N^2-N+1 nor N^2+N+1 is divisible by
    any positive number of the form 6k+5.

--
Don Reble       djr at nk.ca