congruent to 1 mod p

Question

This is a somewhat vague question: for a prime number p, we often see that various counts come out to be 1 modulo p. What are the possible reasons for this?

Here are some I've encountered:

1. For some reason, the counting can be reduced modulo p, or in the field of p elements, and in that setting, the answer turns out to be 1.
2. There is a group action of a p-group on the set with exactly one fixed point. Hence, all the other orbits have sizes equal to a power of p. This is used, for instance, in proving that the number of p-Sylow subgroups is congruent to 1 mod p.
3. A kind of inductive counting argument, that is based on the following observation: the sum of a numbers, each of which is 1 mod p, is congruent to a mod p. Thus, the sum is 1 mod p iff a is 1 mod p. This comes up, for instance, in inductive proofs that the number of subgroups of order $p^k$ in a group of order $p^n$ is congruent to 1 mod $p$. A more general version of this is Phillip Hall's Enumeration Theorem. (This argument can be viewed as a variant of (1), but I find it sufficiently distinctive to mention separately).
4. The number comes up as the number of one-dimensional subspaces of a finite-dimensional vector space over a field with p elements, which we know is a polynomial in p with constant term 1.
5. More sophisticated combinations of (3) and (4) are used to prove that the number of subgroups of various kinds in p-groups is congruent to 1 mod p. See, for instance, the work of Jonah and Konvisser: Counting abelian subgroups of p-groups: a projective approach, Journal of Algebra, Page 309-330, 1975.
6. An application of Fermat's little theorem or a related "order in the multiplicative group" result, wherein a prime q distinct from p can divide $(a^p - 1)/(a - 1)$ only if it is congruent to 1 mod p.
7. Some results on Euler characteristics in combinatorics. I don't really understand how they're proved, or why the "congruent to 1 mod p" comes up.

Looking forward to more situations where "1 mod p" comes up, and/or further insights into the ways I've already mentioned above.

Answer 1

The Chevalley-Warning theorem is proved this way, you count mod p using Fermat's little theorem. Except you show the number of solutions is divisible by p, and if you have a trivial solution then you have another.

http://en.wikipedia.org/wiki/Chevalley-Warning_theorem

Answer 2

If $p\lt q$ are primes, then there is a non-abelian group of order $pq$ if and only if $q$ is 1 (mod $p$).

Answer 3

Let $R_n$ be the number of reduced Latin squares of order $n$. Then $R_n \equiv 1 \pmod n$ if $n$ is prime and $R_n \equiv 0 \pmod n$ if $n$ is composite. See our paper Divisors of the number of Latin rectangles.

In this case, when $n=p$ is a prime, this is arrived at via a group action (by a group of cardinality $p$) that has $(p-2)!$ fixed points. Wilson's Theorem implies $(p-2)! \equiv 1 \pmod p$, giving the result.