Tag Archives: prime power

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

Binomial sum modulo prime power: Part 1

In the last post we showed that

\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p

and then we used Lucas’ theorem to evaluate the sum modulo p.

My initial attempt at evaluating the sum was to note 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}

where \omega=\exp(2\pi i/p), but then I was stuck. Numerical examples suggested that this sum is in fact divisible by p^{\lceil n/(p-1)\rceil}, but I could not think of a way of extending the argument from the last post. Nonetheless, some extensive google search recently revealed that

Theorem (Fleck, 1913). For any j,

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

So taking j=0 gives the desired claim after noting that

Fact. \displaystyle \left\lfloor\frac{n-1}{p-1}\right\rfloor+1=\left\lceil\frac{n}{p-1}\right\rceil.

Proof. Write n=q(p-1)+r with 0\le r<p-1. If r=0 then the equation is just q-1+1=q, and if r>0 then it is q+1=q+1. \square

This article contains a proof of Fleck’s result using the identity (*). Unfortunately I don’t have a good grasp of the theory behind it.


Filed under Number theory

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 from the general exponent lifting result,

Lemma 1. If p is a prime factor of a_k such that p\nmid v, then p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

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)}\Rightarrow 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