hihi, all -
the primes for which period mod p is (p-1) are
11,19,31,41,59, ...
i.e., not all primes - i also get for other primes
mod 3 period 8 2*(p+1)
mod 5 period 20 p*(p-1)
mod 7 period 16 2*(p+1)
mod 11 period 10 p-1
mod 13 period 28 2*(p+1)
mod 17 period 36 2*(p+1)
mod 19 period 18 p-1
mod 23 period 48 2*(p+1)
mod 29 period 14 (p-1)/2
mod 31 period 30 p-1
mod 37 period 76 2*(p+1)
mod 41 period 40 p-1
mod 43 period 88 2*(p+1)
mod 47 period 32 2*(p+1)/3
mod 53 period 108 2*(p+1)
mod 59 period 58 p-1
mod 61 period 60 p-1
mod 67 period 136 2*(p+1)
mod 71 period 70 p-1
mod 73 period 148 2*(p+1)
mod 79 period 78 p-1
mod 83 period 168 2*(p+1)
mod 89 period 44 (p-1)/2
an easy shortcut is to notice that once the value reaches 0 again, the period
is that subscript times the multiplicative order of the next non-zero mod n
(since the recurrence is linear, the values after the next 0 are multiples of
the ones after the first 0)
for example, mod 5 the second 0 occurs at 5 and the surrounding value is 3,
the positive powers of 3 are 3, 4, 2, 1, which occur adjacent to the
subsequent 0's, and the period mod n is 5*4 = 20
the highest ratio i've found of period/n is n=10, period=60
the smallest ratio i've found of period/n is n=9349, period=38
(i only generated them up to 10000 for this check)
the function is also not multiplicative,
since
mod 4 period 6
mod 7 period 16
mod 28 period 48
we also know that the roots of x^2 - x - 1 = 0 mod n are relevant (the
discriminant is 5) - so perhaps it all boils down to the behavior of the
square root(s) of 5 (mod n)
more later,
cal
