Re: HSC 2014 4U Marathon - Advanced Level
Just asking Glittergal, how have you performed in the AMC, UNSW maths comp and the austalian intermediate olympiads/ senior contests (if you've participated)
Quite well, I won't be more specific for the sake of anonymity. I didn't do the AIMO or the UNSW though.
excluding pseudoprimes. Read amended comment above.
there is a way to remove Carmichael primes from showing up, unfortunately it also removes some other numbers.
Divide the LHS by n to remove factor of Carmichael primes.
Add the restriction of n not being equal to p. Or even better n is a prime that is not p. (e.g. 2, 3, 5).
Your last sentence is confusing to me, I will take the following interpretation though I am not 100% sure this is what you mean.
Show that the statement:
"n^(p-1)-1 is divisible by p for all n not divisible by p"
is a necessary and sufficient condition for p to be prime.
First assume p is prime. As discussed before, induction shows n^p-n is then divisible by p for ALL n. But n^p-n=n(n^(p-1)-1). As the RHS is divisible by p and it's first factor isn't, we must have n^(p-1)-1 divisible by p as required. (Note here the fundamental property of primes that if p|xy then p|x or p|y.)
Conversely, suppose p is such that a^(p-1)-1 is divisible by p for all a not divisible by p. Let d =/= p be a factor of p. Since d^(p-1)-1 is divisible by p, it must certainly also be divisible by d. But this would imply that d divides 1. As such, the only factor p can have other than itself is 1...ie p is prime.