Find P = ∏ ( 1 − ω )
where the product is taken over all primitive 2 0 1 5 th roots of unity ω .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
remember we are asuming n not to be 1.
Log in to reply
Yes, exactly: You have written a delightfully general and clear solution! (+1)
Aareyan has written a fine solution. For the sake of variety, let me show another approach.
Note that Φ p ( 1 ) = p for prime p . Now we show by complete induction on n that Φ n ( 1 ) = 1 for square-free n = p 1 ∗ . . . ∗ p m with m > 1 . We write x n − 1 = ∏ d ∣ n Φ d ( x ) , divide by x − 1 , and evaluate at x = 1 to see that n = p 1 ∗ . . . ∗ p m ∗ Φ n ( 1 ) so Φ n ( 1 ) = 1 and P = Φ 2 0 1 5 ( 1 ) = 1 .
This approach easily generalizes to arbitrary n .
Being picky, you need to state that your induction is on m . In the above, you are assuming that m ≥ 3 and that Φ k ( 1 ) = 1 for all k which are the product of between 2 and m − 1 distinct primes.
The ground step m = 2 is needed too; this comes from X p q − 1 = ( X − 1 ) Φ p ( X ) Φ q ( X ) Φ p q ( X ) , so that p q = p × q × Φ p q ( 1 ) .
The inductive step and the ground step are (basically) the same argument, of course; it would be unusual to conflate them without comment, however.
Log in to reply
I should have been more explicit: I'm proving the statement "If n is a composite , square-free integer, then Φ n ( 1 ) = 1 " by complete induction on n , with the base case n = 1 being trivial.
I just tried to do it like this ,
x 2 0 1 5 − 1 = 0 ....... 1) so we need a polynomial whose roots are , 1 − ω ,
so , let 1 − ω = p so ω = 1 − p
Putting this in 1) , we have ,
( 1 − p ) 2 0 1 5 − 1 = 0
after simplification , i did not get the correct answer , was this approach correct ?
Log in to reply
You only want the primitive roots of unity, such that ω k = 1 for k < 2 0 1 5 .
Log in to reply
I didn't get sir @Otto Bretscher
Log in to reply
@A Former Brilliant Member – @Chinmay Sangawadekar , primitive roots of unity means the nth roots of unity in the form of e n 2 k π for GCD(k,n)=1.
P = Φ 2 0 1 5 ( 1 )
Thank you Mobius for your wonderful formula.
We have Φ 2 0 1 5 ( X ) Φ 2 0 1 5 ( 1 ) = d ∣ 2 0 1 5 ∏ ( X d 2 0 1 5 − 1 ) μ ( d ) = ( X 6 5 − 1 ) ( X 1 5 5 − 1 ) ( X 4 0 3 − 1 ) ( X − 1 ) ( X 2 0 1 5 − 1 ) ( X 5 − 1 ) ( X 1 3 − 1 ) ( X 3 1 − 1 ) = ∑ k = 0 4 X 1 3 k ⋅ ∑ k = 0 X 3 1 k ∑ k = 0 4 X 4 0 3 k ⋅ ∑ k = 0 4 X k = 5 ⋅ 5 5 ⋅ 5 = 1
Yes, this is another fine approach! (+1)
Small typo: In the penultimate line, you want sums, not products.
Just to make sure that everybody understands: Why does your approach work despite the fact that the rational function with x − 1 etc. in the denominator is undefined for x = 1 ?
A short solution could be:
Φ 2 0 1 5 ( x ) = Φ 4 0 3 ( x ) Φ 4 0 3 ( x 5 )
then: Φ 2 0 1 5 ( 1 ) = Φ 4 0 3 ( 1 ) Φ 4 0 3 ( 1 5 ) = 1
Your solution is short only because you don't explain your work ;)
Log in to reply
I take for true the fact for p prime not divisor of n we have: Φ p n ( x ) = Φ n ( x ) Φ n ( x p )
Log in to reply
Can you show us a proof or give a reference? The statement is not trivial.
Log in to reply
@Otto Bretscher – Following Wikipedia references, I end up to (Nagell 1951, p. 160)
I don't have access to this reference.
But the proof should not be too hard.
Let P ( x ) = Φ n p ( x ) × Φ n ( x ) and Q ( x ) = Φ n ( x p )
the degree of P(x) is ϕ ( n p ) + ϕ ( n ) = ( p − 1 ) × ϕ ( n ) + ϕ ( n ) = p × ϕ ( n )
the degree of Q(x) is p × ϕ ( n )
So P(x) and Q(x) are monic and have the same degree.
If every complex root of P(x) is root of Q(x) then P(x) = Q(x).
A root α of P(x) is either (np)th primitive root of unity or (n)th primitive root of unity.
In the first case : α = e i 2 π n p k where k coprime with n p
then α p = e i 2 π n k and k coprime with n
In the scond case : α = e i 2 π n k where k coprime with n
then α p = e i 2 π n k p and k p coprime with n since p not divisor of n.
In boot cases α p is (n)th primitive root of unity.
Log in to reply
@Abdelhamid Saadi – Yes, this works; thank you! It is a variant of the proof of a more general result one finds in the literature; for example, Proposition 1.14 here
Log in to reply
@Otto Bretscher – If you like roots of unity, you may enjoy this problem . There is no solution yet...
Log in to reply
@Otto Bretscher – I'll try to find rapidly a solution, since we have only a few hours left in 2015.
And Happy New Year to you and to all Brilliant members.
Log in to reply
@Abdelhamid Saadi – Very few hours indeed (assuming that you are in the US like me). Enjoy!
Happy New Year to you as well.
Problem Loading...
Note Loading...
Set Loading...
the formula is Φ n ( 1 ) = e Λ ( n ) where Λ ( n ) is the von mangoldt function .
consider the basic x n − 1 = d ∣ n ∏ Φ d ( x ) divide by Φ 1 ( x ) = x − 1 . x n − 1 + x n − 2 + . . . + x + 1 = d ∣ n , d > 1 ∏ Φ d ( x ) put x=1 and take log ln ( n ) = d ∣ n , d > 1 ∑ ln ( Φ d ( 1 ) ) let f ( n ) = { 0 ln ( Φ d ( 1 ) ) , n ≤ 1 , n ≥ 2 .and p ( n ) = ln ( n ) .then in dirichlet convolution form: p = f ∗ u . convolute both sides with μ to get: p ∗ μ = f ∗ I = f . in other words: ln ( Φ n ( 1 ) ) = d ∣ n ∑ ln ( d ) μ ( d n ) it is well known ln ( n ) = d ∣ n ∑ Λ ( n ) this is easy to prove, try it yourself. in dirichlet convolution form this is: p = Λ ∗ u . convolute bothsides with μ to get: p ∗ μ = Λ ∗ I = Λ . in other words d ∣ n ∑ ln ( d ) μ ( d n ) = Λ ( n ) . we get that ln ( Φ n ( 1 ) ) = Λ ( n ) or Φ n ( 1 ) = e Λ ( n ) . we are done □ .