[seqfan] Re: Sum of Pell numbers and companion Pell numbers

Fri May 5 16:28:02 CEST 2023

Hi Robert,

Let me first correct an error for the case p == 3,5 (mod 8), when I said (1
+- sqrt(2))^(p+1) == 1 (mod p) and q(p) | (p+1).
In fact, it should be (1 +- sqrt(2))^(p+1) == -1 (mod p) and thus q(p) |
2*(p+1) and not q(p) | (p+1).
For p == 3 (mod 8), it implies that q(p) == 0 (mod 8).
For p == 5 (mod 8), it implies that q(p) == 4 (mod 8).

>From the definition of q(p), we have
(1 +- sqrt(2))^q(p) == 1 (mod p).
And furthermore, if (1 +- sqrt(2))^k == 1 (mod p) for some k, then q(p) | k.

Let m < q(p) be such that a(m) == 0 (mod p), which is equivalent to
(1 + sqrt(2))^(2m) == (-1)^(m+1) (mod p).

Consider two cases:

Case I: m is odd. Then
(1 + sqrt(2))^(2m) == 1 (mod p),
implying that q(p) | 2m, that is, m = q(p) / 2 and thus q(p) == 2 (mod 4).
This case always takes place for p == 7 (mod 8), and may or may not take
place for p == 1 (mod 8).

Case II: m is even. Then
(1 + sqrt(2))^(2m) ==-1 (mod p),
implying that q(p) divides 4m but not 2m, that is, m = q(p) / 4 or m = 3 *
q(p) / 4 (and existence of one zero implies the other), and also q(p) == 0
(mod 8).
This case always takes place for p == 3 (mod 8), and may or may not take
place for p == 1 (mod 8).

Hence we proved that q(p) == 2 (mod 4) or q(p) == 0 (mod 8) are necessary
conditions for existence of zeros of a() modulo p.
It is easy to see that they are also sufficient.

To summarize:
- if p==7 (mod 8), then there is always one zero in the period (Case I).
- if p==5 (mod 8), then there are no zeros (since q(p) == 4 (mod 8));
- if p==3 (mod 8), then there are always two zeros in the period (Case II);
- if p==1 (mod 8), then any number of zeros (0, 1, or 2) is possible.

Just as an example, here is the list of odd primes p < 100 satisfying these
conditions, along with the value of q(p) and the indices of zeros of a()
mod p within the period:
3 8 [2, 6]
7 6 [3]
11 24 [6, 18]
17 16 [4, 12]
19 40 [10, 30]
23 22 [11]
31 30 [15]
41 10 [5]
43 88 [22, 66]
47 46 [23]
59 40 [10, 30]
67 136 [34, 102]
71 70 [35]
73 72 [18, 54]
79 26 [13]
83 168 [42, 126]
89 88 [22, 66]
97 96 [24, 72]

Regards,
Max

On Thu, May 4, 2023 at 10:18 PM Robert Dougherty-Bliss <
robert.w.bliss at gmail.com> wrote:

> Dear Max,
>
> Thanks for the clarification! Forgive me, but I am still confused about
> the rank
> of apparition part of the argument. Why do either m = q(p) / 2 or m = q(p)
> /
> 4 satisfy the identity (1 + sqrt(2))^(2m) (-1)^m == -1 (mod p)? I
> understand
> that m = (p - 1) / 2 or m = (p - 1) / 4 would work, but I don't understand
> why
> we can replace p - 1 with q(p), or why this would be the smallest such m.
>
> It seems like you know where the zeros of a(n) mod p will be, but I can't
> figure out how to find them explicitly.
>
> Thanks again for your help.
>
> Robert
>
> On Sat, Apr 29, 2023 at 8:59 AM Max Alekseyev <maxale at gmail.com> wrote:
> >
> > It all follows from the explicit formula:
> > a(n) = (1 + sqrt(2))^n + (1 - sqrt(2))^n.
> >
> > For an odd prime p, we have
> > (1 +- sqrt(2))^(p-1) == 1 (mod p) whenever 2 is a quadratic residue
> modulo
> > p, ie. p == 1,7 (mod 8);
> > and
> > (1 +- sqrt(2))^(p+1) == 1 (mod p) whenever 2 is a non-quadratic residue
> > modulo p, ie. p == 3,5 (mod 8).
> > It follows that the period length q(p) of a() modulo p divides p-1 or
> p+1,
> > respectively.
> >
> > Then, a(m) == 0 (mod p) is equivalent to
> > (1 + sqrt(2))/(1-sqrt(2))^m = (1 + sqrt(2))^(2m) * (-1)^m == -1 (mod p).
> > If m is the smallest, ie. m = r(p) is the rank of apparition, then r(p) =
> > q(p)/2 when it's odd; or r(p) = q(p)/4 when it's even.
> > In the former case, there is only one zero in the period modulo p, ie. if
> > a(m) == 0 (mod p) and q(p)/2 is odd, then m == q(p)/2 (mod q(p)) and thus
> > q(p)/2 divides m.
> > In the latter case, there are two zeros in the period modulo p, ie. if
> a(m)
> > == 0 (mod p) and q(p)/4 is even, then m == q(p)/4 (mod q(p)/2) and thus
> > q(p)/4 divides m.
> >
> > Let me know if anything is still unclear.
> >
> > Regards,
> > Max
> >
> > On Sat, Apr 29, 2023 at 2:51 AM Robert Dougherty-Bliss <
> > robert.w.bliss at gmail.com> wrote:
> >
> > > Dear Max,
> > >
> > > Thank you for the proof! I am excited about it, because this is
> > > exactly what I suspected was true. However, I'm having some trouble
> > > following the details of your argument.
> > >
> > > > Let p be the smallest prime dividing m and r(p) the rank of
> apparition of
> > > > a() modulo p, then the period of a() modulo p is either 2*r(p) or
> 4*r(p),
> > > > and it divides p-1 or p+1.
> > >
> > > Why is the period either 2 * r(p) or 4 * r(p)? And why does it divide
> > > p - 1 or p + 1?
> > >
> > > > That is, r(p) <= (p+1)/2 < p and r(p) divides m, which together with
> > > > minimality of p implies r(p)=1.
> > >
> > > Why does r(p) divide m?
> > >
> > > I know some similar facts / arguments about Fibonacci numbers, but I
> > > don't see how the ideas apply here.
> > >
> > > Robert
> > >
> > > > On Thu, Apr 27, 2023 at 11:05 PM Robert Dougherty-Bliss <
> > > > robert.w.bliss at gmail.com> wrote:
> > > >
> > > > > Dear Sequence Fans,
> > > > >
> > > > > Consider the sequence a(n) which satisfies the recurrence
> > > > >      a(n) = 2 * a(n - 1) + a(n - 2)
> > > > > with initial conditions a(0) = a(1) = 2. (This is A2203, the
> companion
> > > > > Pell numbers.)
> > > > >
> > > > > The sequence of positive n such that a(n) = 2 (mod n) begins
> > > > > 1, 2, 3, 4, 5, 7, 8, 11, 13, 16, 17, 19, 23, 24, 29.
> > > > > Except for the leading 1 and 2, this looks like A270342, the
> sequence
> > > > > of n such that n divides the sum of the first n Pell numbers, but
> > > > > there is no comment to this effect. Can anyone prove this?
> > > > >
> > > > > The sum of the first n Pell numbers S(n) turns out to equal (a(n)
> - 2)
> > > > > / 4, so everything in A270342 is in this sequence. For the other
> way,
> > > > > I have managed to prove that if a(n) = 2 (mod n) and n is odd or
> > > > > divisible by 4, then n is in A270341, but I cannot figure out the
> > > > > "divisible by just 2" case.
> > > > >
> > > > > Robert
> > > > >
> > > > > --
> > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > >
> > > >
> > > > --
> > > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>