Problem 437

[tomboy]

I think I understood the problem, yet I'm only able to verify 9 fibonacci primitive roots for primes <10000:
2,3,5,7,11,13,17,19,29.

Did I understand it correctly, that for p to have a primitive root n,
- (n^x % p) has to be cyclic
- cycling with period (p-1)
- and the cycle having all numbers [1..p-1]?

[mpiotte]

I think I understood the problem, yet I'm only able to verify 9 fibonacci primitive roots for primes <10000:
2,3,5,7,11,13,17,19,29.

Did I understand it correctly, that for p to have a primitive root n,
- (n^x % p) has to be cyclic
- cycling with period (p-1)
- and the cycle having all numbers [1..p-1]?

You're criteria for n being a primitive root of p is correct.
However, your test for the Fibonacci behavior must be wrong.

Lets take p=2. The only primitive root of 2 is 1, and {1^k} = {1, 1, 1, 1, 1, ... }. Now 1 + 1 &ne; 1 modulo 2, so p=2 has no Fibonacci primitive root.

Let take p=3. The only primitive root is 2, and {2^k}={1,2,1,2,1,2...}. Now 1 + 2 &ne; 1 modulo 3, so p=3 has no Fibonacci primitive root.

Similarly 7, 13, 17 and 29 have no Fibonacci primitive root. 5, 11 and 19 do, as well as 320 others less than 10000.

[KING-OLE]

Just making sure I understand this.

Must fpr<p?

If so, for p<10000, the only solution I get is the one shown as the example, where p=11 and fpr=8.

If I however allow fpr<100000, I find 2 solutions, and if fpr<1000000, I find 3.

I am confused.

Thanks.

[traxex]

Must fpr<p?

Yes, you may assume that a primitive root modulo $p$ is less than $p$.

If so, for p<10000, the only solution I get is the one shown as the example, where p=11 and fpr=8.

You should be able to find many examples with an exhaustive brute force search.

[KING-OLE]

You should be able to find many examples with an exhaustive brute force search.

Thanks.

Hmm, then obviously I am doing something wrong somewhere.

I have a brute force test looping through all p's < 10,000 and all fpr's < p, and the example (11,8) is the only result I get.

Back to the drawing board.