Counting subgroups of a $p$-group. Let $G$ be a finite $p$-group, say $|G|=p^n$, and let $0\le k\le n$. Call $\mathcal{A}$ the set of subgroups of order $p^k$, and $\mathcal{N}\subseteq\mathcal{A}$ the subgroups that are normal.
I want to show that $|\mathcal{A}|\equiv |\mathcal{N}|\equiv 1 \pmod{p}$.
I define $\phi:G\times\mathcal{A}\to\mathcal{A}$ by $\phi(g,H)=gHg^{-1}$. Let $O(H_1),...,O(H_n)$ the orbits whose union is $\mathcal{A}$.
But I don't see why $|O(H_1)|+...+|O(H_n)|\equiv 1\pmod{p}$.
On the other hand, to see that $|\mathcal{A}|\equiv |\mathcal{N}| \pmod{p}$, there exists a set $\{i_{1},...,i_{k}\}\subseteq\{1,...,n\}$ such that:
$\mathcal{A}\setminus\mathcal{N}=O(H_{i_1})\cup ...\cup O(H_{i_k})$, so I'd like to show that $p$ divides all the $|O(H_{i_j})|$, but again I don't know how to do this.
Any hint? Thanks.
 A: I recall your notations. Define $\phi \colon G\times\mathcal{A} \to \mathcal{A}$ by $\phi(g,H) = gHg^{-1}$. We choose $H_1,\ldots,H_n$ in $\mathcal{A}$ such the orbits $O(H_1),\ldots,O(H_n)$ are disjoint and such that $\mathcal{A} = \bigcup_{i=1}^n O(H_i)$.
Therefore, $|\mathcal{A}|=\sum_{i=1}^n|O(H_i)|$. Now, we use the fact that $H \in \mathcal{N}$ if and only if $O(H) = \{H\}$. You then have :
$$|\mathcal{A}| = |\mathcal{N}| + \sum_{1\leq i \leq n, O(H_i)\neq\{H_i\}}|O(H_i)|.$$
Can you see why $p$ divides $|O(H_i)|$ when $O(H_i)\neq \{H_i\}$ ?
A: Showing that $|\mathcal{A}| \equiv |\mathcal{N}| \mod{p}$ from the work you've already shown follows from the fact that the orbit $|O(H)|$ under the conjugation action is equal to the index of the normalizer $|G:N_G(H)|$ by the orbit-stabilizer theorem.  If $H$ is not normal, then this index is a non-trivial power of $p$, and thus the order of the orbit is divisible by $p$.
The way I figured out the rest of the problem uses induction on $k$.  It is somewhat involved (and I can't see a cleaner proof), so I will give a sketch.  
For $k=1$, I use a different method.   Partition $G$ via the equivalence $g \sim g'$ if $\langle g\rangle = \langle g' \rangle$, and then counting the total modulo $p$.  You need to check that each subgroup of order $p$ corresponds to an equivalence class of size $p-1$, and the only remaining equivalence class whose order is not divisible by $p$ is the equivalence class $\{e\}$ of the identity.
For the inductive step, I count (modulo $p$) the number of pairs $(P,Q)$ of normal subgroups $P,Q$ with $|P| = p^{k-1}, |Q| = p^k, P\subset Q$.  Count these pairs in two ways, first by choosing $Q$ and subsequently all corresponding $P$, and second by choosing $P$ and subsequently all corresponding $Q$.  You can have an equation relating the total number of $Q$ to the following:


*

*The total number of $P$.

*For each $P$, the number of such $Q$ containing $P$.

*For each $Q$, the number of such $P$ contained in $Q$.


Examine the sum to note that if all of these are congruent to $1$ modulo $p$, so too is the total number of $Q$.  The first of these is congruent to $1$ inductively.  The second is also congruent to $1$ by considering the normal subgroups of $G/P$ and using the $k=1$ case.  
The third is also congruent to 1, but requires an argument.  You inductively know that the number of subgroups $H\le Q$ with $|H| = p^k$ is congruent to $1$ modulo $p$, and you need to show that the number of such $H$ that are normal as subgroups of $G$ is also congruent to 1 modulo $p$.  This argument uses $G$'s conjugation actions on subgroups of $Q$ and is otherwise identical to the $|\mathcal{A}| \equiv |\mathcal{N}|$ argument above.
