Tag Archives: ideal

Binomial Sum Modulo Prime Power: Part 2

Let p be a prime number and \omega=\exp(2\pi i/p). Recall that we conjectured in this post that

(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}

is divisible by p^{\lceil n/(p-1)\rceil}. From exercise 2 of this post we know that (p) factors as (p,\omega-1)^{p-1} into prime ideals in the ring \mathbb Z[\omega]. So (\omega-1)^{p-1}\in (p). Therefore the right-hand side of (*) is divisible by p^{\lfloor n/(p-1)\rfloor}. So we are off by at most one factor of p! I believe this approach can be improved upon to account for the extra factor, since we haven’t used any property of the sum.


\displaystyle\sum_{j=0}^{p-1}\omega^{-rj}(1-\omega^j)^n=p\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}

for any r. So our best result thus far is the following:

Theorem (weaker version of Fleck’s).

\displaystyle\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\lfloor\frac{n}{p-1}\rfloor-1}}.

Goal: Improve the floors to ceilings.

Leave a comment

Filed under Algebra, Number Theory

Ring of Integers of Cyclotomic Field

Let \zeta=\zeta_n=e^\frac{2\pi i}{n} be a primitive n-th root of unity, and let K=\mathbb Q(\zeta). I am going to outline a proof that \mathcal O_K=\mathbb Z[\zeta], based on several homework problems from one of my recent courses. There are probably many other proofs of this, but I particularly like this one because it’s easy to follow, touches on a wide range of topics, and I worked hard through it!

First, let n=p^m be a prime power. The minimal polynomial of \zeta is the n-th cyclotomic polynomial


Let f(X)=\Phi_n(X+1).

Exercise 1. Following the above notation, show that f satisfies the conditions of Eisenstein’s criterion for the prime p.

Consider the discriminant \Delta(f)=\Delta(R), where R=\mathbb Z[\zeta-1]. If q is a prime factor of \Delta(f), then f must have a multiple root modulo q. Hence X^{p^m}-1 will also have a multiple root modulo q. But \gcd(X^{p^{m}}-1, p^{m}X^{p^{m}-1})=1 in \mathbb Z/q\mathbb Z unless q=p. Thus \Delta(f)=\Delta(R)=[\mathcal O_K:R]^2\Delta(\mathcal O_K) is a power of p. In particular, [\mathcal O_K:R] is a power of p.

Exercise 2. Suppose that f\in\mathbb Z[X] satisfies the conditions of Eisenstein’s criterion for a prime number p. Let \alpha be a root of f and let R=\mathbb Z[\alpha]. Prove that there is exactly one prime ideal P\subseteq R that contains p, and that the local ring R_P is a DVR with uniformiser \alpha.

Now if Q\subseteq R is another prime ideal, then p\not\in Q. So [\mathcal O_K:R]\not\in Q.

Exercise 3. Let K be a number field and R\subseteq\mathcal O_K a subring of finite index d. If Q\subseteq R is a prime ideal not containing d, show that R_Q is a DVR.

I’ll include this solution because I love it!

Solution. Let D=\mathcal O_K. By going up, there is a prime ideal \tilde Q\subseteq D with \tilde Q\cap R=Q. We’ll show that D_{\tilde Q}=R_Q, so the result will follow.

Let a/b\in R_Q, so that a\in R, b\in R\setminus Q. If b\in \tilde Q, then b\in R\cap \tilde Q=Q, a contradiction. Hence b\not\in\tilde Q, i.e. a/b\in D_{\tilde Q}. Thus R_Q\subseteq D_{\tilde Q}.

Now let a/b\in D_{\tilde Q}, so that a\in D, b\in D\setminus\tilde Q. Then da\in R, db\in R, and a/b=(da)/(db). Note that b\not\in\tilde Q\supseteq Q, and d\not\in Q by assumption. So db\not\in Q since Q is a prime ideal. Thus a/b=(da)/(db)\in R_Q, i.e. D_{\tilde Q}=R_Q. \square

So R localised at any prime ideal is a DVR, implying that R=\mathbb Z[\zeta] is a Dedekind domain. Thus R=\mathcal O_K. This completes the proof for the prime power case.

Now we proceed by induction on the number of distinct prime factors of n. The base case has already been taken care of. So suppose that n=ab, where a,b>1 are coprime integers. Let L=\mathbb Q(\zeta_a) and M=\mathbb Q(\zeta_b). By the induction hypothesis, \mathcal O_L=\mathbb Z[\zeta_a] and \mathcal O_M=\mathbb Z[\zeta_b].

Exercise 4. Let L and M be number fields with discriminants \lambda and \mu respectively. Let \{a_1,\dots,a_m\} and \{b_1,\dots,b_n\} be integral bases for L and M respectively. Let K=LM=\mathbb Q(a_1,\dots,a_m,b_1,\dots,b_n) be the composite field of L and M. Suppose that [K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q] and that \gcd(\lambda,\mu)=1. Show that \{a_ib_j:1\le i\le m; 1\le j\le n\} is an integral basis for K.

So our main result will follow from exercise 4 once we have checked that all the hypotheses are satisfied.

(i) Checking K=LMFirstly, LM contains \zeta_a\zeta_b=e^{\frac{2\pi i(a+b)}{n}}=\zeta^{a+b}.

Exercise 5. If \gcd(a,b)=1, show that \gcd(a+b,ab)=1.

So writing j=a+b shows that \gcd(j,n)=1 and \zeta^j\in LM. If j^{-1}\in\{1,\dots,n\} is the multiplicative inverse of j\pmod n, then \zeta=(\zeta^j)^{j^{-1}}\in LM. Thus K\subseteq LM.

Again, since \zeta^a=\zeta_b and \zeta^b=\zeta_a, we have LM\subseteq K. Thus K=LM.

(ii) Checking [K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q]. We have

[K:\mathbb Q]=\varphi(n)=\varphi(ab)=\varphi(a)\varphi(b)=[L:\mathbb Q][M:\mathbb Q].

(iii) Checking \gcd(\lambda,\mu)=1This is slightly harder. We need a few more facts.

Exercise 6. Let E=\mathbb Q(\alpha) be a number field, and let f be the minimal polynomial of \alpha. Show that

\Delta(\alpha)=(-1)^{\binom{\deg(f)}{2}}N_{E/\mathbb Q}(f'(\alpha)).

Solution. Let f(x)=(x-\alpha_1)\cdots(x-\alpha_n). Then

\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_{i\neq j}(\alpha_i-\alpha_j)=(-1)^{\binom n2}\prod_i\prod_{j\neq i}(\alpha_i-\alpha_j).

Using Leibniz’s rule,

\displaystyle f'(x)=\sum_i\prod_{j\neq i}(x-\alpha_i)\Rightarrow f'(\alpha_i)=\prod_{j\neq i}(\alpha_i-\alpha_j).


\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_if'(\alpha_i)=(-1)^{\binom n2}N_{E/\mathbb Q}(f'(\alpha)). \square

Exercise 7. Using the previous exercise, show that \Delta(\zeta_n)\mid n^{\varphi(n)}.

Hint. Write X^n-1=\Phi_n(X)g(X), and use Leibniz’s rule to get n\zeta_n^{n-1}=\Phi_n'(\zeta_n)g(\zeta_n).

So \lambda=\Delta(\zeta_a) divides some power of a, and \mu=\Delta(\zeta_b) divides some power of b. Since \gcd(a,b)=1, we conclude that \gcd(\lambda,\mu)=1.

1 Comment

Filed under Algebra, Number Theory

Minimum Number of Prime Ideals

Let K be an algebraically closed field and R=K[x,y]. Let J=(P(x),Q(y)) \subseteq R be an ideal. Since R is noetherian, a theorem of Noether says that there are finitely many prime ideals p_1,\dots,p_n\supseteq J such that p_1\cdots p_n\subseteq J.

Suppose that P(x)=(x-a)^A(x-b)^B and Q(y)=(y-c)^C are uniquely factored into irreducibles. Then each p_i is equal to (x-a,y-c) or (x-b,y-c). Suppose that r of them are (x-a,y-c) and s of them are (x-b,y-c). Then

\displaystyle p_1\cdots p_n=\left((x-a)^i(x-b)^j(y-c)^k:\begin{cases}0\le i\le r\\ 0\le j\le s\\ 0\le k\le r+s\\ i+j+k=r+s\end{cases}\right)

To have p_1\cdots p_n\subseteq J, therefore, we need

\{k\ge C\}\cup(\{i\ge A\}\cap\{j\ge B\}).

So we need k\ge C or \min\{i,j\}\ge\max\{A,B\}, i.e.

k+\min\{i,j\}\ge C+\max\{A,B\}-1

\begin{aligned}\Leftrightarrow n=r+s&=k+\min\{i,j\}+\max\{i,j\}\\ &\ge C+\max\{A,B\}-1+\max\{i,j\}.\end{aligned}

As i,j,k vary, we may replace \max\{i,j\} with \max\{r,s\}. We therefore deduce:

Bound 1. \min\{r,s\}\ge C+\max\{A,B\}-1.

Bound 2. n\ge 2(C+\max\{A,B\}-1).

Remark. Bound 1 is obviously stronger; however, since in general we don’t have information on r and s, bound 2 is uniformly the best possible.

The calculation becomes much more subtle for general polynomials.

Leave a comment

Filed under Algebra

Some Divisibility Properties of Fibonacci-Like Sequences

Here we shall aim to generalise the corollary from the last post, and on the way generalise some other important properties of the Fibonacci sequence, to general Fibonacci-like sequences.

Consider a sequence \{a_n\} with a_0=0, a_1=1 and a_n=ua_{n-1}+va_{n-2} for n\ge 2, where u,v\in\mathbb Z such that u^2+4v\neq 0. Let \alpha,\beta be the roots of x^2-ux-v=0. Then

\displaystyle a_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}.

Let p be an odd prime. Suppose (\alpha) and (p) have a common factor. By Dedekind’s Factorisation Criterion, (p) is either prime or it factors into two (not necessarily distinct) prime ideals each with norm p. In the first case, we must have (p)\mid (\alpha) i.e. p^2\mid v, taking ideal norms. In the second case, if one of the prime factors of (p) divides (\alpha), then (again taking norms) p must divide v.

So we take (p,v)=1 which ensures that (\alpha) and (p) are coprime. Thus we deduce the following from Theorem 2 of this post.

Lemma 1. If p is a prime factor of a_k such that p\nmid v, then for all n\ge 0,

p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}.

Next, recalling the proof of the corollary from last time, we seem to require the condition (a_m,a_n)=a_{(m,n)}.

Lemma 2. If (u,v)=1, then (a_m,a_n)=a_{(m,n)} for all m,n.

Proof. First, it is clear that (a_m,a_n)/a_{(m,n)}\in\mathcal O_K, where K=\mathbb Q(\alpha), and that (a_m,a_n)/a_{(m,n)}\in\mathbb Q. Thus (a_m,a_n)/a_{(m,n)}\in\mathbb Z.

Let p be a prime factor of (a_m,a_n). Then for m\ge n,

\displaystyle p\mid\frac{\alpha^m-\beta^m}{\alpha-\beta}-\frac{\alpha^{m-n}(\alpha^n-\beta^n)}{\alpha-\beta}=\frac{\beta^n(\alpha^{m-n}-\beta^{m-n})}{\alpha-\beta}=\beta^na_{m-n}.

If (p) and (\beta^n) share a common factor, then (taking ideal norms,) p\mid v. Hence a_n\equiv ua_{n-1}\equiv u^{n-1}\equiv 0\pmod p, a contradiction as (u,p)=1.

Hence (a_m,a_n)\mid a_{m-n} and by the Euclidean algorithm we get (a_m,a_n)\mid a_{(m,n)}. Thus (a_m,a_n)=a_{(m,n)}, as desired. \square

Now we define k(n) to be the least k such that n\mid a_k, and we are ready for our generalisation!

Theorem. Let \{a_n\} be given by a_0=0,a_1=1 and a_n=ua_{n-1}+va_{n-2} for n\ge 2, where u,v are coprime integers such that u^2+4v\neq 0. Then for an odd prime p for which k(p) exists,

p^r\parallel a_{k(p)}\implies k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}

Proof. If p\mid v, then p\mid a_{k(p)}-va_{k(p)-2}=ua_{k(p)-1}. By definition of k(p), p\nmid a_{k(p)-1}. Hence p\mid u, which is impossible as (u,v)=1. Thus p\nmid v and the proof of the corollary in the previous post now applies. \square

Leave a comment

Filed under Algebra, Number Theory

A Generalisation of ‘Lifting the Exponent’

Lifting the Exponent is a popular result in elementary number theory. It basically says the following.

Theorem 1. (Lifting the Exponent) Let \alpha,\beta\in\mathbb Z and put


Then for an odd prime p coprime to \alpha,\beta, and for r\ge 1,

p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}

for all integers n\ge 0.

Here, as usual, p^r\parallel x means that p^r\mid x but p^{r+1}\nmid x.

We generalize Theorem 1 to general rings of algebraic integers.

Theorem 2. Let K be an algebraic number field and \mathcal O_K its ring of integers. Let \alpha,\beta\in\mathcal O_K such that the ideals (\alpha), (\beta) are coprime to (p), and


is an integer for all integers n\ge 0. Then

p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}

for all integers r\ge 1 and n\ge 0.

Proof. We proceed by induction on n. The base case n=0 is clear. Suppose that the assertion holds for n-1. We want to show that p^{n+r}\parallel a_{kp^n}, that is,

\displaystyle p^{n+r}\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha-\beta}=a_{kp^{n-1}}\cdot\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}

By hypothesis, p^{n+r-1}\parallel a_{kp^{n-1}}. So we need to show that \displaystyle p\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}.

Let c=\alpha^{kp^{n-1}}, d=\beta^{kp^{n-1}}. We want to show that \displaystyle p\parallel\frac{c^p-d^p}{c-d}.

Since p\mid a_k, we have a_k\in (p). Hence \alpha^k-\beta^k=(\alpha-\beta)a_k\in (p), i.e. \alpha^k\equiv\beta^k\pmod p. Hence c\equiv d\pmod p. Let c=d+\mu p for some \mu\in\mathcal O_K. Then

\displaystyle\frac{c^p-d^p}{c-d}=\frac{(d+\mu p)^p-d^p}{\mu p}=\frac{p\cdot d^{p-1}\mu p+\cdots}{\mu p}\equiv pd^{p-1}\pmod{p^2}.

If this is 0, then (p)\mid (d)^{p-1}, which is impossible by unique factorisation as (p) and (d) are coprime. \square

Corollary. Let \{F_n\} be the Fibonacci sequence. Then

p^r\parallel F_{k(p)}\implies k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}

(Refer to this post for notation.)

Proof. Take \alpha=\varphi=\frac{1+\sqrt 5}{2}, \beta=\bar\varphi=\frac{1-\sqrt 5}{2} (with K=\mathbb Q(\sqrt 5) and \mathcal O_K=\mathbb Z[\varphi]) and let k=k(p). We proceed by induction on n. Suppose p^{n+r}\mid F_j for some j<kp^n. By hypothesis, k(p^{n+r-1})=kp^{n-1} so p^{n+r-1}\mid p^{n+r}\mid F_j\implies kp^{n-1}\mid j<kp^n. Then 1\le \frac{j}{kp^{n-1}}<p, so \gcd(\frac{j}{kp^{n-1}},p)=1, i.e. \gcd(j,kp^n)=kp^{n-1}. Hence \gcd(F_{kp^n},F_j)=F_{kp^{n-1}} which implies p^{n+r}\mid F_{kp^{n-1}}, a contradiction. \square


Filed under Algebra, Number Theory