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?



Sequences satisfying gcd(S(x), S(y)) = S(gcd(x,y))
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. 


