Ok, here's the proof that I know (not by me).

First, let's get the definition clear.

My definition: a cycle of length p is a set with p elements {v0,v1,v2,...,vp-1} such that v1 is friend with v0, v2 is friend with v1, ..., vp-1 is friend with vp-2, v0 is friend with vp-1. The set Sp is the collection of all such p-cycles. Note, different starting point corresponds to different p-cycle. Also note, v0,v1,...,vp-1 don't have to be different from each other. e.g. if v0 and v1 are friends, we can have {v0,v1,v0,v1,v0,v1,....}

A path of length p-1 is a set with p-1 elements {v0,v2,...,v(p-2)} such that v1 is friend with v0, v2 is friend with v1, ..., v(p-2) is friend with v(p-3). L is the set of all such p-1 paths. Again, v0,v1,...don't have to be different. Also note that my p-1 path is one element shorter than fzy's p-1 path.

Our previous result shows that if there's no politician, then, everyone has k friends. and k is even. Also, N = k(k-1)+1. Since k is even, k-1 is odd, and there's an odd prime factor of k-1. We pick one of such odd prime factor and denote it with p.

Now, the proof:

It is obvious that |Sp| is divisible by p, since every cycle can have p different starting point: {v0,v1,v2,...,v(p-1),v0},{v1,v2,...,v(p-1),v0,v1}, etc.

Now, we will show |Sp| is not divisible by p.

Consider the set L. It is obviously that there are N*k^(p-2) such p-1 paths. There are N choices for the starting point, after that, each next one has k choices, thus, total of N*k^(p-2). There are two kinds of p-1 path in L. One kind is v(p-2)=v0, the other kind is v(p-2) != v0. We denote the set of the first kind as L1, the set of the second kind as L2. There's a correspondance between L and Sp. Every Sp can be gotten by adding an element to a p-1 path. For any p-1 path in L1, there are k different ways to get to a p cycle. For any p-1 path in L2, there is one unique way to get to a p cycle, since v(p-2) and v0 can only have a unique friend. Thus,

|Sp| = k*L1 + L2 = (k-1)*L1 + L1 + L2 = (k-1)*L1 + N*k^(p-2), we know that N = 1(mod k-1), k = 1(mod k-1), thus, the second term above cannot be divisible by p, thus, |Sp| cannot be divisible by p. QED.

Notice that once we get the definitions clear, the actual proof is very straight forward, I like this approach very much.