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.

Furthermore,

$\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.

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

$\displaystyle\Phi_n(X)=\Phi_{p^m}(X)=\sum_{j=0}^{p-1}X^{jp^{m-1}}$.

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=LM$Firstly, $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)=1$This 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)$.

Hence

$\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. 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$