mod 6

Don Reble djr at nk.ca
Sun Mar 16 05:53:18 CET 2003

```> 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

```