## Problem 437

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
tomboy
Posts: 5
Joined: Sun Sep 01, 2013 8:24 am

### Problem 437

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
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm

### Re: Problem 437

tomboy wrote: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
Posts: 10
Joined: Mon Dec 22, 2014 9:33 pm

### Re: Problem 437

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
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

### Re: Problem 437

KING-OLE wrote:
Mon Apr 16, 2018 1:49 pm
Must fpr<p?
Yes, you may assume that a primitive root modulo $p$ is less than $p$.
KING-OLE wrote:
Mon Apr 16, 2018 1:49 pm
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.
Technically, everyone is full of himself.

KING-OLE
Posts: 10
Joined: Mon Dec 22, 2014 9:33 pm

### Re: Problem 437

traxex wrote:
Mon Apr 16, 2018 3:30 pm
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.