More fun in 2015, Part 45

Find P = ( 1 ω ) P=\prod(1-\omega)

where the product is taken over all primitive 201 5 th 2015^\text{th} roots of unity ω \omega .


The answer is 1.

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.

4 solutions

Aareyan Manzoor
Dec 28, 2015

the formula is Φ n ( 1 ) = e Λ ( n ) \Phi_n(1)=e^{\Lambda(n)} where Λ ( n ) \Lambda(n) is the von mangoldt function .


consider the basic x n 1 = d n Φ d ( x ) x^n-1=\prod_{d\mid n} \Phi_d(x) divide by Φ 1 ( x ) = x 1 \Phi_1(x)=x-1 . x n 1 + x n 2 + . . . + x + 1 = d n , d > 1 Φ d ( x ) x^{n-1}+x^{n-2}+...+x+1=\prod_{d\mid n,d>1} \Phi_d(x) put x=1 and take log ln ( n ) = d n , d > 1 ln ( Φ d ( 1 ) ) \ln(n)=\sum_{d|n,d>1}\ln(\Phi_d(1)) let f ( n ) = { 0 , n 1 ln ( Φ d ( 1 ) ) , n 2 f(n)=\begin{cases} 0&&,n≤1\\\ln(\Phi_d(1))&&,n≥2\end{cases} .and p ( n ) = ln ( n ) p(n)=\ln(n) .then in dirichlet convolution form: p = f u p=f*u . convolute both sides with μ \mu to get: p μ = f I = f p*\mu=f*I=f . in other words: ln ( Φ n ( 1 ) ) = d n ln ( d ) μ ( n d ) \ln(\Phi_n(1))=\sum_{d|n} \ln(d)\mu\left(\dfrac{n}{d}\right) it is well known ln ( n ) = d n Λ ( n ) \ln(n)=\sum_{d|n} \Lambda(n) this is easy to prove, try it yourself. in dirichlet convolution form this is: p = Λ u p=\Lambda*u . convolute bothsides with μ \mu to get: p μ = Λ I = Λ p*\mu=\Lambda*I=\Lambda . in other words d n ln ( d ) μ ( n d ) = Λ ( n ) \sum_{d|n} \ln(d)\mu\left(\dfrac{n}{d}\right)=\Lambda(n) . we get that ln ( Φ n ( 1 ) ) = Λ ( n ) \ln(\Phi_n(1))=\Lambda(n) or Φ n ( 1 ) = e Λ ( n ) \Phi_n(1)=e^{\Lambda(n)} . we are done _\square .

remember we are asuming n not to be 1.

Aareyan Manzoor - 5 years, 5 months ago

Log in to reply

Yes, exactly: You have written a delightfully general and clear solution! (+1)

Otto Bretscher - 5 years, 5 months ago
Otto Bretscher
Dec 28, 2015

Aareyan has written a fine solution. For the sake of variety, let me show another approach.

Note that Φ p ( 1 ) = p \Phi_p(1)=p for prime p p . Now we show by complete induction on n n that Φ n ( 1 ) = 1 \Phi_n(1)=1 for square-free n = p 1 . . . p m n=p_1*...*p_m with m > 1 m>1 . We write x n 1 = d n Φ d ( x ) x^n-1=\prod_{d|n}\Phi_d(x) , divide by x 1 x-1 , and evaluate at x = 1 x=1 to see that n = p 1 . . . p m Φ n ( 1 ) n=p_1*...*p_m*\Phi_n(1) so Φ n ( 1 ) = 1 \Phi_n(1)=1 and P = Φ 2015 ( 1 ) = 1 P=\Phi_{2015}(1)=\boxed{1} .

This approach easily generalizes to arbitrary n n .

Being picky, you need to state that your induction is on m m . In the above, you are assuming that m 3 m \ge 3 and that Φ k ( 1 ) = 1 \Phi_k(1) = 1 for all k k which are the product of between 2 2 and m 1 m-1 distinct primes.

The ground step m = 2 m=2 is needed too; this comes from X p q 1 = ( X 1 ) Φ p ( X ) Φ q ( X ) Φ p q ( X ) X^{pq}-1 = (X-1)\Phi_p(X)\Phi_q(X) \Phi_{pq}(X) , so that p q = p × q × Φ p q ( 1 ) pq = p \times q \times \Phi_{pq}(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.

Mark Hennings - 5 years, 5 months ago

Log in to reply

I should have been more explicit: I'm proving the statement "If n n is a composite , square-free integer, then Φ n ( 1 ) = 1 \Phi_n(1)=1 " by complete induction on n n , with the base case n = 1 n=1 being trivial.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

I can live with that!

Mark Hennings - 5 years, 5 months ago

I just tried to do it like this ,

x 2015 1 = 0 x^{2015}-1=0 ....... 1) so we need a polynomial whose roots are , 1 ω 1-\omega ,

so , let 1 ω = p 1-\omega = p so ω = 1 p \omega=1-p

Putting this in 1) , we have ,

( 1 p ) 2015 1 = 0 (1-p)^{2015}-1=0

after simplification , i did not get the correct answer , was this approach correct ?

@Otto Bretscher

A Former Brilliant Member - 5 years, 5 months ago

Log in to reply

You only want the primitive roots of unity, such that ω k 1 \omega^k\neq 1 for k < 2015 k<2015 .

Otto Bretscher - 5 years, 5 months ago

Log in to reply

I didn't get sir @Otto Bretscher

A Former Brilliant Member - 5 years, 5 months ago

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 2 k π n e^{\dfrac{2k\pi}{n}} for GCD(k,n)=1.

Aareyan Manzoor - 5 years, 5 months ago
Alan Yan
Dec 29, 2015

P = Φ 2015 ( 1 ) P = \Phi_{2015}(1)

Thank you Mobius for your wonderful formula.

We have Φ 2015 ( X ) = d 2015 ( X 2015 d 1 ) μ ( d ) = ( X 2015 1 ) ( X 5 1 ) ( X 13 1 ) ( X 31 1 ) ( X 65 1 ) ( X 155 1 ) ( X 403 1 ) ( X 1 ) = k = 0 4 X 403 k k = 0 4 X k k = 0 4 X 13 k k = 0 X 31 k Φ 2015 ( 1 ) = 5 5 5 5 = 1 \begin{aligned} \Phi_{2015}(X) & = \prod_{d | 2015}(X^{\frac{2015}{d}} - 1)^{\mu(d)} \\ & = \frac{(X^{2015} - 1)(X^{5} - 1)(X^{13} -1)(X^{31} - 1)}{(X^{65} - 1)(X^{155} - 1)(X^{403} - 1)(X-1)} \\ & = \frac{\sum_{k = 0}^{4}{X^{403k}} \cdot \sum_{k = 0}^{4}{X^k}}{\sum_{k = 0}^{4}{X^{13k}} \cdot \sum_{k = 0}{X^{31k}}} \\ \Phi_{2015}(1) & = \frac{5 \cdot 5}{5 \cdot 5} = \boxed{1} \end{aligned}

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 x-1 etc. in the denominator is undefined for x = 1 x=1 ?

Otto Bretscher - 5 years, 5 months ago
Abdelhamid Saadi
Dec 31, 2015

A short solution could be:

Φ 2015 ( x ) = Φ 403 ( x 5 ) Φ 403 ( x ) \Phi_{2015}(x)= \frac{\Phi_{403}(x^5)}{\Phi_{403}(x)}

then: Φ 2015 ( 1 ) = Φ 403 ( 1 5 ) Φ 403 ( 1 ) = 1 \Phi_{2015}(1)= \frac{\Phi_{403}(1^5)}{\Phi_{403}(1)} = 1

Your solution is short only because you don't explain your work ;)

Otto Bretscher - 5 years, 5 months ago

Log in to reply

I take for true the fact for p prime not divisor of n we have: Φ p n ( x ) = Φ n ( x p ) Φ n ( x ) \Phi_{pn}(x)= \frac{\Phi_{n}(x^p)}{\Phi_{n}(x)}

Abdelhamid Saadi - 5 years, 5 months ago

Log in to reply

Can you show us a proof or give a reference? The statement is not trivial.

Otto Bretscher - 5 years, 5 months ago

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 ) P(x) = \Phi_{np}(x) \times \Phi_{n}(x) and Q ( x ) = Φ n ( x p ) Q(x) = \Phi_{n}(x^{p})

the degree of P(x) is ϕ ( n p ) + ϕ ( n ) = ( p 1 ) × ϕ ( n ) + ϕ ( n ) = p × ϕ ( n ) \phi(np) + \phi(n) = (p - 1)\times \phi(n) + \phi(n) = p \times \phi(n)

the degree of Q(x) is p × ϕ ( n ) p \times \phi(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 α \alpha 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 π k n p \alpha = e^{i2\pi\frac{k}{np}} where k k coprime with n p np

then α p = e i 2 π k n \alpha^p = e^{i2\pi\frac{k}{n}} and k k coprime with n n

In the scond case : α = e i 2 π k n \alpha = e^{i2\pi\frac{k}{n}} where k k coprime with n n

then α p = e i 2 π k p n \alpha^p = e^{i2\pi\frac{kp}{n}} and k p kp coprime with n n since p p not divisor of n.

In boot cases α p \alpha^p is (n)th primitive root of unity.

Abdelhamid Saadi - 5 years, 5 months ago

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

Otto Bretscher - 5 years, 5 months ago

Log in to reply

@Otto Bretscher If you like roots of unity, you may enjoy this problem . There is no solution yet...

Otto Bretscher - 5 years, 5 months ago

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.

Abdelhamid Saadi - 5 years, 5 months ago

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.

Otto Bretscher - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...