Sorry, an error occurred while loading the content.
Browse Groups

• ## Re: [PrimeNumbers] Thinking caps on again

(7)
• NextPrevious
• ... Erm, it was, but I don t see how such a response could possibly invoke my wrath! I was simply wondering how many different approaches there were. ... [SNIP
Message 1 of 7 , Aug 20, 2006
View Source
--- Peter Kosinar <goober@...> wrote:
> > Prove, for the n-th cyclotomic polynomial evaluated at i, Phi(n,i)
> >
> > Phi(n,1) = { p if n=p^i, prime p, i>0
> > { 0 if n=1
> > { 1 otherwise
>
> Risking Phil's wrath if this was intended just as a simple exercise,

Erm, it was, but I don't see how such a response could possibly invoke my
wrath!
I was simply wondering how many different approaches there were.

> here's my (hopefully correct) solution to the problem. If you want to
> solve it yourself, don't read further ;-)
[SNIP - easy cases]
> The remaining case (composite-non-prime-power n) is now provable by simple
> induction. Let's split the product on the right-hand side of
> x^n - 1 = product[d divides n] Phi(d, x)
> into four parts:
> 1) Phi(n, x) itself
> 2) Phi(1, x) = (x-1)
> 3) Phi(p1, x) * Phi(p1^2, x) * ... * Phi(p1^e1, x) *
> Phi(p2, x) * Phi(p2^2, x) * ... * Phi(p2^e2, x) *
> ...
> Phi(pk, x) * Phi(pk^2, x) * ... * Phi(pk^ek, x) *
> (where n = p1^e1 * p2^e2 * ... * pk^ek is the complete factorization
> of n)
> 4) the product of remaining terms (possibly none) Phi(d, x), where all d's
> are composite non-prime-powers smaller than n.
>
> According to the analysis above, the product of group 3 is equal to n
> (each term adds one prime), all terms in group 4 are equal to 1 according
> to the induction hypothesis (thus their product is also equal to 1) so
> dividing the whole equality by Phi(1,x) yields:
>
> (x^n - 1) / (x - 1) = Phi(n, x) * n
>
> The left-hand side can be expanded as sum[0 <= m < n] x^m and
> evaluation at x=1 yields Phi(n,x) = 1.

That's a pretty good method, I like it as it doesn't resort to anything that I
couldn't explain to my dad, say.

Using the properties exploited in the p^k step, one only needs to consider
products of distinct primes, but that doesn't really shorten the proof.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.