3
$\begingroup$

Consider the sequence S(x) = 2^x - 1. This sequence has two interesting properties:

a) If the GCD of S(x) and S(y) is S(gcd(x,y)), and

b) For any prime p, S(p-1) is divisible by p.

Property a follows from the fact that if 2^x is 1 mod n and 2^y is 1 mod n, 2^(gcd(x,y)) is 1 mod n. Property b follows from Fermat's little theorem.

I am interested in sequences that exhibit property a but also have a modified form of property b such as b*) For any prime p, S(p-2) is divisible by p.

Does anyone know of any such sequences?

Improve this question
$\endgroup$
2
  • $\begingroup$ There are many such sequences, a^n - 1 being a form which leads to the study of cyclotomic polynomials. The Fibonacci numbers (and certain other solutions of recurrences) are a disguised form of a^n - b^n, and also have the property. I do not know the most general form of such sequences. Gerhard "Ask Me About System Design" Paseman, 2013.05.25 $\endgroup$
    – Gerhard Paseman
    Commented May 25, 2013 at 18:28
  • $\begingroup$ well, those sequences satisfy the first property but not the second one. For example, if $p|a^{p-2}-b^{p-2}$ then $p|a-b,$ which holds only for finitely many $p.$ $\endgroup$
    – Alvin
    Commented May 25, 2013 at 18:35

1 Answer 1

Reset to default
8
$\begingroup$

A strong divisibility sequence is a sequence of positive integers $(a_n)_{n\ge1}$ with the property that $\gcd(a_n,a_m)=a_{\gcd(n,m)}$. See http://en.wikipedia.org/wiki/Divisibility_sequence. (Strong) divisibility sequences tend to arise from algebraic groups, including sequences such as $a^n-b^n$, Fibonacci (and similar) sequences, elliptic divisibility sequences, etc. I'm not sure about your second condition. For elliptic divisibility sequences, there's a large literature on which terms are divisible by $p$, but it generally won't be the $(p-2)$'nd term. See http://en.wikipedia.org/wiki/Elliptic_divisibility_sequence, especially the section on EDS over finite fields.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .