I’m not convinced this is MO-appropriate, but I’m posting an answer ’cause what I’d have to say is probably too long for a comment.
Expanding on Reid’s comment. Yeah, Lucas’ theorem is nice. Lucas’ theorem is one of a fair number of combinatorial results which can be thought of as “first steps towards p-adic numbers.” What’s that mean? There’s a “different” absolute value that you can define on rational numbers, which has a lot of the same properties as the usual absolute value, but in other ways behaves totally differently. Actually there are an infinite number of these guys, one for every prime $p$! It’s called the p-adic absolute value, and you can read about it on Wikipedia.
What the p-adic numbers do is help you to get around the following obstacle: Say you want to tell whether a quotient of two numbers, $\frac{a}{b}$, is divisible by $p$. (We’ll assume for now that $\frac{a}{b}$ is definitely an integer, although this ends up not mattering at all. But “divisibility” is a trickier notion for non-integers.) If $a$ is divisible by $p$ and $b$ isn’t, then it’s obvious that $\frac{a}{b}$ is; if $a$ isn’t divisible by $p$, then of course $\frac{a}{b}$ isn’t. But things get tough if both $a$ and $b$ are divisible by $p$; it could happen that $a$ is divisible by $p^2$, and $b$ is divisible by $p$ but not by $p^2$. Or that $a$ is divisible by $p^{17}$, and $b$ is divisible by $p^{14}$ but not by $p^{15}$. You see how this gets confusing! The p-adic absolute value encodes this sort of information for you.
This also explains why we don’t work with, say, 10-adic numbers in mathematics; it’s because if you take the integers but consider two integers to be the same if they have the same remainder when you divide by $n$, you can still multiply and add and subtract perfectly well. So you get something called a ring. And if $n$ is prime, you can also divide numbers! (Well, you can’t divide by 0, or by a multiple of the prime, which is “the same as” 0. But this is true no matter what, so it’s not a real problem.) But this isn’t true for composites.
Anyway, the patterns for primes in Pascal’s triangle are pretty well known. Google “Pascal’s triangle modulo” (without quotes, probably) to find more stuff. Composites don’t behave as nicely, for the reasons Wikipedia and I both briefly mentioned, but powers of primes do have interesting patterns, which you can read about in the wonderfully-titled paper “Zaphod Beeblebrox’s Brain and the Fifty-ninth Row of Pascal’s Triangle”.
Hope this helps!
Here's a massive generalization, with references.
Consider a sequence $\{a_n \}_{n\ge 1}$ of integers. We'll say it satisfies the necklace congruences if $a_{n} \equiv a_{n/p} \mod n$ whenever $p \mid n$ ($p$ prime).
Here are some equivalent formulations:
- $a_{p^{k+1} m} \equiv a_{p^k m} \mod {p^{k+1}}$ for all $p,m,k$
- $\sum_{d \mid n} a_d \mu(n/d) \equiv 0 \mod n$ for all $n$
- The Mobius function can be replaced by any arithmetic function $f$ satisfying $\sum_{d \mid n} f(d) =0 \mod n, f(1) = \pm 1$.
So any such sequence gives rise to an integer sequence $\lambda_{\tilde{a}}(n) := \frac{1}{n}\sum_{d \mid n} a_d \mu(n/d)$ which satisfies $a_n = \sum_{d \mid n} d \lambda_{\tilde{a}}(n)$ by Mobius inversion. One can then define $\sigma_{\tilde{a}}(n):=\sum_{d \mid n, 1<d<n} d\lambda_{\tilde{a}}(d)$ and obtain the following generalization of Fermat's little theorem:
$a_n \equiv a_1 + \sigma_{\tilde{a}}(n) \mod n$
Now, let's go back to necklace congruences. A less obvious equivalence is the following:
Theorem: $\{a_n\}_{n \ge 1}$ satisfies the necklace congruences iff $\zeta_{a}(x):=\exp(\sum_{n\ge1} \frac{a_n}{n}x^n)$ has integer coefficients.
Proof: Write, $\zeta_a$ formally as $\prod_{n\ge 1} (1-x^n)^{-\frac{b_n}{n}}$. The $b_n$'s are uniquely determined, and in fact (by taking logarithmic derivative) it can be seen that they are $b_n = \sum_{d \mid n} a_d \mu(n/d)$. Now one direction is immediate and the other requires an inductive argument. $\blacksquare$
(Reference: Exercise 5.2 (and its solution) in Richard Stanley's book "Enumerative Combinatorics, vol. 2")
As Sergei remarked, for any integer square matrix $A$, the sequence $a_n := \text{Tr}(A^n)$ satisfies the necklace congruences. This is immediate from the last theorem, as the corresponding "zeta" function $\zeta_a$ is just:
$\exp( \sum_{n \ge 1} \frac{\text{Tr}((Ax)^n)}{n}) = \exp (\text{Tr} (- \ln (I -Ax)))=\det(I-Ax)^{-1} \in \mathbb{Z}[x]$
In particular, by taking a 1 on 1 matrix, we recover your observation.
Another generalization is $a_n = [x^n]f^n(x)$, where $f \in \mathbb{Z}[[x]]$. By taking the linear polynomial $f(x)=1+ax$ we recover your example, by taking $f(x)=(1+x)^m$ we get $a_n = \binom{nm}{n}$.
The really interesting feature is that this notion has a local version. Specifically, theorems of Dieudonne-Dwork and Hazewinkel give the following result:
Theorem: Given $\{ a_n \}_{n\ge 1} \subseteq \mathbb{Q}_{p}$ ($p$-adic numbers), the following are equivalent:
- $\zeta_{a}(x) := \exp(\sum_{n\ge 1} \frac{a_n }{n}x^n)\in\mathbb{Z}_{p}[x]$
- $\exp( \sum_{n \ge 1} p \frac{a_n - a_{n/p}}{n} x^n) \in 1+px\mathbb{Z}_{p}[x]$ (I defnite $a_{n/p}=0$ if $p\nmid n$)
- $\sum_{n \ge 1} \frac{a_n - a_{n/p}}{n} x^n) \in \mathbb{Z}_{p}[x]$
- $p \mid n \implies a_n \equiv a_{n/p} \mod {n\mathbb{Z}_{p}}$
Applying this simultaneously for all $p$, we recover the previous theorem.
A reference for this theorem is "A Course in p-adic Analysis" by Alain M. Robert (the theorems are stated there in a much more general context).
Best Answer
Let just try a look at your first result:
Corollary 1 in Johnson, Wells paper above says:
Let $\epsilon = 1,-1$ and let $p=2^r+ \epsilon$ be a prime number. Then
$$ q_p(2) \equiv \frac{\epsilon}{r} \pmod{p} $$
Your result for a Mersenne prime (taking $\epsilon =-1$ above) follows from this:
Observe that (trivially) $2^r \equiv 1 \pmod{p}$. Thus $2^r-2 \equiv -1 \pmod{p}$
In other words:
$$ 2q_r(2) \equiv (2^r -2) \frac{1}{r} \equiv (-1) \cdot \frac{1}{r} \equiv \frac{\epsilon}{r} \equiv q_p(2) \pmod{p} $$
Thus $$ q_p(2) \equiv 2q_r(2) \pmod{p}. $$