[seqfan] Re: Odd behavior in a sequence

[israel at math.ubc.ca]

The solution of the recurrence with initial conditions a(0)=0, a(1)=1 is

a(n) = (s^n - t^n)/sqrt(17)

where s = (3+sqrt(17))/2 and t = (3-sqrt(17))/2 = -2/s. This works in any 
field (not of characteristic 2 or 17) where 17 has a square root. Thus if p 
is an odd prime and 17 is a quadratic residue mod p, say 17 == b^2 mod p, 
we have a(n) == (s^n - t^n)/b mod p where s == (3+b)/2 and t == -2/s. Now 
by Fermat's little theorem, a(n) is periodic in n with period at most p-1, 
so in this case it's impossible to cover all the residues.

On the other hand, if 17 is not a quadratic residue mod p, you go to an 
extension field, and it's possible that all residues will be covered. 
However, this is not guaranteed. Thus for p = 683, s and t have order 396, 
so at most 396 of the residues are covered (in fact only 177 are).

Note, by the way, that by quadratic reciprocity 17 is a quadratic residue 
mod the odd prime p iff p is a quadratic residue mod 17, i.e. p == 1, 2, 4, 
8, 9, 13, 15, or 16 mod 17.

Cheers,
Robert

On Oct 20 2015, David Wilson wrote:

>I'm looking at the linear recurrence
>
> 
>
>0, 1, 3, 11, 39, 139, .
>
> 
>
>with a(n) = 3a(n-1) + 2a(n-2) for n >= 2.
>
> 
>
> I was interested in the question, for which primes p do {a(n)} == Z (mod 
> p)?
>
>
>That is, for which primes p do all residues r appear in {a(n)} (mod p)
>(Forgive my notational abuse)?
>
>We'll shorten that to "a covers p".
>
> 
>
>I expected this to have a simple answer, and it almost does.
>
>It turns out that whether or not a covers p most of the time depends on p
>mod 17.
>
>In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 7).
>
> 
>
>However, there seem to be a smattering of primes p:
>
> 
>
>683, 1217, 2731, 11299, 48817, .
>
> 
>
>which, according to their residue mod 17, should be covered by a, but are
>not.
>
>Very curious.
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>