Cyclotomic Polynomials in Olympiad Number Theory

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Cyclotomic Polynomials in Olympiad Number Theory

G H J

Reveal topic tags

abstract algebra

L

G H BBookmark kLocked kLocked NReply

Source: dinoboy

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#1 h Jan 23, 2013, 10:33 PM • 96 Y

Y by baijiangchen, pi37, v_Enhance, Kouichi Nakagawa, PolyaPal, AndrewKwon97, r31415, AkshajK, giratina150, math154, hyperbolictangent, El_Ectric, dantx5, dan23, Binomial-theorem, iarnab_kundu, turkeybob777, negativebplusorminus, GlassBead, exmath89, EricMathPath09, NewAlbionAcademy, kprepaf, siddigss, Amir Hossein, antimonyarsenide, Liebig, Zeref, RiteshR, aZpElr68Cb51U51qy9OM, AwesomeToad, tc1729, proglote, Aref, yugrey, shekast-istadegi, airplanes1, tahanguyen98, Maxima, Pinphong, cire_il, qua96, Potla, pgmath, ahaanomegas, forthegreatergood, bcp123, sicilianfan, Tuxianeer, acupofmath, BOGTRO, Arangeh, Torus121, subham1729, joybangla, minimario, fractals, henrikjb, john111111, fclvbfm934, TheCrafter, mikechen, huricane, hamup1, Wave-Particle, Eugenis, ptxpotterhead, tenplusten, enhanced, XbenX, fatant, mathleticguyyy, AlastorMoody, mathlogician, OlympusHero, myh2910, vsamc, NicoRicci, Flying-Man, Adventure10, Mango247, and 15 other users

Hello everyone,

Over the past few months I have written an article developing much of the theory on Cyclotomic Polynomials and many applications to Olympiad math. Its been almost finished for the past few weeks, but schoolwork delayed me finishing it for a very long time but now it is finished! There are extremely interesting and applicable to a pretty reasonable set of Olympiad Number Theory problems.

Below is a link to a copy in dropbox, however for some reason the hyperlinks don't render correctly on it which is pretty annoying. Because of this, a copy of the article is also attached to this post which hopefully the hyperlinks work correctly on.
I have also attached the tex file for my article in case they do not render correctly on the pdf, because then you can compile the document yourself. It also is attached to serve as a LaTeX sort of guide, because I myself struggled for quite a while to learn sufficient LaTeX to make a pdf which looked nice.

If you find any errors/typos, please e-mail me or private message the errors to me so I can correct them. Posting them onto this thread is fine as well, but I would prefer you not do that because I want this thread to be used for discussion of the exercises.

I hope you enjoy this article!

P.S.

Dropbox Version

EDIT : I have attached newer versions of the tex file/pdf now.
EDIT2: I have attached even newer versions.

Attachments:

Cyclotomic Polynomials.pdf (320kb)

Cyclotomic Polynomials.tex (53kb)

This post has been edited 4 times. Last edited by dinoboy, May 16, 2014, 8:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#2 h Jan 23, 2013, 11:10 PM • 15 Y

Y by baijiangchen, kprepaf, siddigss, ArefS, Binomial-theorem, Adventure10, Mango247, and 8 other users

This is great, thanks. I won't comment yet on the math because I've only had a few minutes to skim the article, but I'll point out the typos I've seen in a brief scan:

"Its ok if you ... " in the remark about UFD's.
"Note a key aspect we have above : we had no restictions"
Problem 1 from British MO: looks like you tried to copy a "fi" ligature from a PDF. The word "infinite" is broken.

Also, being a LaTeX geek, I can't help but point out a few things. (In all honesty the LaTeX is making my eyes bleed.)
Rant

You may be interested in the following commands:

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

This will also mitigate the need for all the "

" everywhere.

Also, there is a built-in command

\begin{proof} This is a proof.  A QED box will be added at the end \end{proof}

which can also do

\begin{proof}[Solution] This replaces "Proof." with "Solution." \end{proof}

You can use \addtolength{\parindent}{0.2cm} instead of \hspace{0.2cm} everywhere. Also, if you are going to put

... end of paragrah. 
\indent Next paragraph

you should just use

... end of paragraph.
 
Next paragraph

which is essentially equivalent.

Also, you are doing the hyperlinks completely wrong. Try the following:

\begin{thm}[Zsigmondy's Theorem]
$\forall a,n > 1 \exists p: \ord_p(a) = n$.
\label{thm:zsig}
\end{thm}
... blah ...
By Theorem \ref{thm:zsig} we win.

If you share the Dropbox file with me, I would be happy to clean up the LaTeX for you. Shoot me a PM.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#3 h Feb 18, 2013, 6:07 AM • 4 Y

Y by kundu, Adventure10, Mango247, and 1 other user

I have added 3 exercises to the article and corrected a few typos

P.S.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

979 posts

#4 h May 4, 2013, 6:36 PM • 2 Y

Y by Adventure10, Mango247

Do you mean the following in exercise 5?

Prove that the minimal polynomial of $\cos \left (\frac{2\pi}{n}\right )$ has degree $\frac{\varphi (n)}{2}.$ I haven't heard about the irreducible polynomial of $\cos \left (\frac{2\pi}{n}\right ).$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#5 h May 4, 2013, 9:42 PM • 1 Y

Y by Adventure10

Yes! I have corrected the error. Currently the error is only corrected on the dropbox file, I will update the attached pdf and tex file when more changes have been made.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1020 posts

#6 h May 11, 2013, 5:30 PM • 2 Y

Y by Adventure10, Mango247

Is the dropbox file always the latest and most up to date?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#7 h May 11, 2013, 5:31 PM • 4 Y

Y by mentalgenius, Adventure10, Mango247, and 1 other user

Yes, because it's Dropbox. Dropbox has the convenient property that the file is automatically updated everywhere whenever you save. So if dinoboy saves a change, then all references everywhere get updated automatically.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#8 h Oct 14, 2013, 3:03 PM • 1 Y

Y by Adventure10

Can somebody post solutions to the proposed exercises?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#9 h Nov 25, 2013, 9:05 PM • 2 Y

Y by Adventure10, Mango247

Thanks for the article. Section 2.3, where you ask if the coefficients of all Cyclotomic polynomials are either -1,0 or 1, the answer is negative. The case n=105 gives the first counter-example to that statement, but your explanations give the reader the idea that he/she should try to prove that all coefficients are indeed from the set {-1,0,1} which is false and therefore can't be proven. So, I think you need to mention it to save people's time before they start to attempt to prove something which is false.

Also, when you talk about Cyclotomic polynomials over the field Zp in section 5, maybe it's me, but there is still ambiguity about how they are defined. Do you define them as the way they've already been calculated over Z[x] and then you work with them over Zp[x] by using the canonical epi-morphism from Z[x] to Zp[x]? It'd be easier to understand if you mention how they're defined explicitly.

(I'm new here. How can I type LaTeX codes on this forum?)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#10 h Nov 25, 2013, 9:49 PM • 3 Y

Y by a_math_geek, Adventure10, and 1 other user

The reason why I don't tell the reader whether its true or false is because in trying to prove it is true you can motivate a lot of the identities in Section 3. These in turn motivate you to look at $\Phi_{pqr}(x)$ for $p,q,r$ odd primes after one proves it is true for $\Phi_{pq}(x)$ , and it turns out the first example gives you a counterexample. Perhaps you might toil around wasting your time chasing something which is wrong, but finding the intermediate results will help solidify your understanding a lot.

You are correct that I never explicitly mentioned how I define $\Phi_n(x)$ over $\mathbb{Z}_p$ . They are defined as taking the integer polynomial in mod $p$ , and then reducing its coefficients mod $p$ (i.e. exactly what you are saying). When I have more time I'll edit this into my article.

To use LaTeX on the forum look here.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

148 posts

#11 h Dec 29, 2013, 3:40 AM • 2 Y

Y by Adventure10, Mango247

Is this a counterexample to 3.5?

Consider $\Phi_3(2^3) = 8^2 + 8 + 1 = 73$ .

This is equal to $\prod_{d|3}\Phi_{3d}(2) = \Phi_3(2)\Phi_9(2) = (2^2 + 2 + 1)(2^6 + 2^3 + 1) = 7\cdot 73 \ne 73$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1583 posts

#12 h Dec 29, 2013, 3:45 AM • 2 Y

Y by Adventure10, Mango247

$\gcd(3, 3) \neq 1$ , so your counterexample doesn't apply.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#13 h Dec 29, 2013, 8:34 PM • 2 Y

Y by Adventure10, Mango247

No, you do not. The article was written to be understandable only knowing concepts in Olympiad mathematics.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4216 posts

#14 h Jan 19, 2014, 10:59 PM • 1 Y

Y by Adventure10

Can you post a proof of Theorem 3.1? The linked page referenced in the proof seems to be broken.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1221 posts

tc1729

#15 h Jan 19, 2014, 11:07 PM • 2 Y

Y by Adventure10, Mango247

Hello, see here. But, you don't really need to take logs -- the Mobius inversion formula works multiplicatively for any Abelian group.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a