Problems & Puzzles: Puzzles

Puzzle 538. (3n^2+3n+1) ^2 | (3n+1)^(3n+2) + 3n+2 Farideh Firoozbakht says that Maximilian Hasler has proved that: (3n^2+3n+1) ^2 | (3n+1)^(3n+2) + 3n+2 Q. Can you send your own proof?

---

Contributions came from Gurmeet Singh & Emmanuel Vantieghem.

***

Gurmeet wrote:

I have to prove that ((3n^2+3n+1)^2)|(3n+1)^(3n+2)+(3n+2)   -----------eq1
let x=3n+1,eq1 become
=> ((x^2+x+1)^2) | 9(x^(x+1)+x+1) where x=3n+1

and x^(x+1)+x+1=(1+x+x^2)+(x^(x-1)-1)x^2
                      =(1+x+x^2)+(x-1)(1+x+x^2+.......+x^(x-2))x^2
                      =(1+x+x^2)+(x-1)(1+x+x^2+.......+x^(3n-1))x^2

=(1+x+x^2)+(x-1)(1+x+x^2)(1+x^3+x^6+.......+x^(3(n-1)))x^2
                      =(1+x+x^2)(1+(x-1)(1+x^3+x^6+.......+x^(3(n-1)))(x^2))

let y=(x^(x+1)+x+1)/(x^2+x+1)=1+(x^3-x^2)(1+x^3+x^6+.........+x^(3(n-1)))
now eq1 become (x^2+x+1)|9y

as  (x^3-x^2)=(x+2) (mod (x^2+x+1))
and (x^(3k)-1)=0 (mod x^3-1) where k is an integer

=>  x^3k=1 (mod x^3-1)
=>  x^3k=1 (mod (x-1)(x^2+x+1))
=>  x^3k=1 (mod (x^2+x+1))

=>  9y=9+9(x+2)(1+1+1+1+.....n times) (mod (x^2+x+1))
=>  9y=9+9(3n+1+2)(n) (mod (3(3n^2+3n+1)))
=>  9y=9(3n^2+3n+1) (mod (3(3n^2+3n+1)))
 

=>  9y=0 (mod 3(3n^2+3n+1))
 

=>  9y=3c(3n^2+3n+1)) where c is an integer
or   9y=c(x^2+x+1)
=>  (x^2+x+1)|9y
=>  ((3n^2+3n+1)^2)|(3n+1)^(3n+2)+(3n+2)
hence proved...

And as
y=(3n^2+3n+1) (mod 3(3n^2+3n+1))
from it we get a more stronger result
(3n+1)^(3n+2)+(3n+2)=3(3k+1)((3n^2+3n+1)^2)
where k is an integer.

***

Emmanuel wrote:

Consider the quadratic polynomial  W = 3x^2+3x+1.  Then, it is easy (!) to prove by induction on  n, the following polynomial congruences :
      (3x+1)^(3n+2) +3x+2 == 3(3nx+3n+1)W ( mod 3W^2 ).
Putting  x = n  gives the desired divisibility property (with the additional factor 3).

I prefer to ommit the details of the induction proof.  I simply mention that I made use of the following helpfull identities :
            (3x+1)^3 = 9xW+1    and    x(3x+2) = w-x-1.
 

***