Problems & Puzzles: Puzzles

Puzzle 166. pⁿ -1 =0 mod f(n)

Jean-Christophe Colin, French, wrote the following puzzle:

It's easy to prove that:

p, prime>3 then p^2-1=0 mod 24
p, prime>5 then p^4-1=0 mod 240
p, prime>7 then p^6-1=0 mod 504
p, prime>5 then p^8-1=0 mod 480
and too p, prime>2 then p^3-1=0 mod 2

Q: Find a general law that says "p, prime >q(n) then pⁿ-1 = 0  mod f(n)"

Solution:

Eric Brier sent (30/9/02) the following solution to this puzzle:

a) the theory behind his solution in a .pdf paper
b) an example to clarify the application of the theory developed

The example goes like this:

Let n=12. Then:

The set of the divisors of n is D(n)={1,2,3,4,6,12}

The set of primes equal to each divisor of n plus 1 is P(n)={2,3,5,7,13}

1) f(n) is the product of every prime in P to a power calculated this way:

• for odd primes in P: power is 1+a; a= max such that p^a divides n

• for prime=2: power is 2+a; a= max such that p^a divides n

For n= 12 this means:

f(12) = 2^4*3^2*5*7*13 = 65520

2) q(n) is equal to the largest prime of f(n). For n=12 this means that q(12)=13

In short: for all p=prime>13, p^12 = 1 mod 65520

***

A small historical note

Exactly the same solution was found by the author of this puzzle, J. C. Colin, who sent two days before (28/9/02) a description if his method and a Table of solutions for n even from 2 to 150 and other selected values up to 1000. As a matter of fact, he discovered the method by analyzing the Table values, produced by a code from his own:

"...I think I found a law who answers to the question of puzzle 166. I am a little disappointed I, my self, found the solution of my question but I simply found watching the table n, f(n),q(n) I built with an Ubasic program... the method I found to calculate f(n) and q(n) when n  is know, seems more like cooking as mathematics but it works!"

Facing the Colin's disappointment I wrote to him the same 28/9/02:

1) I'm asking one talented puzzler in congruences to try your puzzle but without showing him already your method.

2) If he fails to find the law, I will submit your method to him again - if you agree - in order he review it. Is it OK?

Two days later came the Eric's solution who needed not at all to know the Colin's solution, indeed.

***