Define the function recursively by: Prove that is divisible by for all
If n is prime therefore which is divisible by n according to Fermat's little theorem
Fermat's little theorem - Wikipedia, the free encyclopedia
First, that recurrence relation determines completely the numbers , and they are in fact given by: -by Möbius' inversion formula.
Okay, but the path we will take is rather different. Consider the primitive strings of bits of length (*) these happen to satisfy the same recurrence relation, hence they must be equal - from what I said above-.
(*) A string is not primitive if it is a concatenation of smaller ( all of them equal) strings. For example is not a primtive string, since it's made out of
Take for instance, this is a primitive string of bits of length 3. Next note that if we 'move' the places by 1 to the right ( and the last one goes to the first, a sort of circular permutation) we get: which is another primitive string of length 3, and if we do it again we get: which is again a primitive string. Note also that if we do it again we get to the initial one.
So this suggests that we can partition the set of primitive strings of length into sets of elements in which each of the primitive strings is obtained by applying the operation -the operation has a name but it's on the tip of my tongue, oh well, I'll call it Circular permutation- we have just used repeatedly to a certain primtive string. (clearly an equivalence relation)
First, it's easy to see that this operation applied to a primitive string generates another ( suppose the contrary and you'll get a contradiction by using a method similar to the one below.)
We have to show that indeed we have sets of different strings, always.
So, suppose we have a primitive string of length , which we will assoctiate with a function were we have:
Suppose that applying our operation repeatedly times we get to the same initial string, which is equivalent to the condition: then
Now consider , and the integer division: ; , since we get: , hence, if r is not 0 we have: which is a contradiction, hence and
But this implies that our primitive string is a concatenation of smaller, and equal, strings of length , thus it's not a primitive string: CONTRADICTION
Now if represents a string of length n, let be the string of length n resulting from doing the operation on .
We've just seen that, for any primitive string of length n, , for all (1)
So consider that for a primitive string we have that are not all different, that is for some , then and we get a contradiction by using (1), since we know that is also a primitive bit string of length n
Therefore the claim is proven since we have where is the number of equivalence classes.
that's an interesting combinatorial approach PaulRS. the problem has also an algebraic solution:
Fact: the number of monic irreducible polynomials of degree over a finite field with elements, where is prime, is:
i encourage anyone who's new to algebra (and number theory) to think about this beautiful result and see if they can prove it!