Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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

share|improve this answer
4  
You can make this a "1 mod p" statement: If d<=n, then the number of F_p-points on a hypersurface of degree d in P^n over F_p is 1 mod p. This can be given a cohomological interpretation and generalized to other classes of varieties, as in recent work of Hélène Esnault and others. –  Bjorn Poonen Feb 7 '10 at 20:12

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$).

share|improve this answer
    
And one implication of this follows from the third Sylow theorem as mentioned by the OP :-) –  Robin Chapman Jun 29 '10 at 11:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.