- http://www.mathpages.com/home/kmath347/kmath347.htm

claims that the first exception to the conjecture that

n is a prime if and only if f(r**n) = 0 (mod n)

where r is any root of f(x) = x**5 - x**3 - 2x**2 + 1.

is n = 2258745004684033 = 27439297 * 82317889.

What is x**n mod n if

x**5 = x**3 + 2 x**2 - 1?

what procedure would be used to calculate

the roots x**n mod n

when x is constrained to satisfy

x**5 = x**3 + 2 x**2 - 1?

x**6 = x**4 + 2 x**3 - x

x**7 = x**5 + 2 x**4 - x**2

x**7 = (x**3 + 2 x**2 - 1) + 2 x**4 - x**2

x**7 = 2 x**4 + x**3 + (2 - 1) x**2 - 1

x**8 = 2 x**5 + x**4 + (2 - 1) x**3 - x

x**8 = 2 [x**3 + 2 x**2 - 1] + x**4 + (2-1) x**3 - x

x**8 = x**4 + (2+ 2 - 1) x**3 + (2 * 2) x**2 - x - 2*1

Clearly this implies a recurrence relation on the

coefficients of x**4, x**3, x**2, x, and 1.

Then it is clear that

x**n = 0 mod n if and only if

x**n = a4 x**4 + a3 x**3 + a2 x**2 + a1 x + a0

is, in mod n, some polynomial multiple of

x**3 + 2 x**2 - 1 .

2 x**4 + x**3 + (2 - 1) x**2 - 1

2 x**4 + x**3 + x**2 - 1

(x**3+2 x**2 -1)(b4 x**4 +b3 x**3 +b2 x**2 +b1 x + b0) =0 mod 7

reduces to a 4th degree equation = 0 mod 7,

which supposedly determines unique values of

b4, b3, b2, b1, b0.

It is reasonable to guess that if n is prime,

that the corresponding b4,b3,b2,b1,b0 can always

be solved mod n,

but if n is not prime, it might not be possible

to solve for the b4,b3,b2,b1,b0.

It is still not clear what algorithm had probably been used to prove

that x**n is not 0 mod n for each composite number tested.

Another approach:

f(x) = x**5 - x**3 - 2x**2 + 1.

f(x**2) = x**10 - x**6 - 2 x**4 + 1

= x**10 - x**6 + 1 mod 2

f(x**3) = x**15 - x**9 - 2 x**6 + 1

= x**15 - x**9 - 2 x**6 + 1 mod 3

Is this polynomial = 0 mod 3?

supposedly we could use the recurrence relations to reduce

f(x**m) to a fourth degree polynomial, and determine whether or not it

is equivalent to 0 mod m.

Does anyone see a simpler approach?

Kermit - On 11/5/2010 2:22 PM, Maximilian Hasler wrote:
>

Yes. I am ok with using the language of

> On Fri, Nov 5, 2010 at 10:18 AM, djbroadhurst<d.broadhurst@...> wrote:

>>

>>

>> --- In primenumbers@yahoogroups.com,

>> Kermit Rose<kermit@...> asked:

>>

>>> Is it true that for every positive prime p,

>>> that in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),

>>> that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?

>

> This is a valid formulation ; not so, to my eyes, the one in terms of

> the roots of that polynomial, which are irrational numbers x=r[i] for

> which e.g. p*x is not an element of pZ<=> congruent to zero (mod p).

>

> M.

>

ring polynomial mod ( particular polynomial, integer).

I will not quibble with you about whether or not it is valid to

define parity for numbers in algebraic extensions of integers mod 2.

Now that that is settled, how about my question?

>>> Is it true that for every positive prime p,

Kermit

>>> that in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),

>>> that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?