Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $r$ be an integer greater than $2$. Is there a simple way of showing that $2^r$ divides $\left(\begin{array}{c} {2}^{r-2} \\ k \end{array}\right) 2^{2k}$ but it does not divide $\left(\begin{array}{c} 2^{r-l} \\ k \end{array}\right) 2^{2k}$ for $l>2$ and for all $k$ greater than $0$ and less or equal than $2^{r-2}$?

Equivalently, is there a simple way of showing that the element $5$ has order $2^{r-2}$ in the group of units of the ring $\mathbb{Z}_{2^r}$?

The two questions are connected by writing $5 = 4 + 1$ and using the binomial expansion formula to study the order of $5$.

share|cite|improve this question
The highest power of $p$ that divides $\binom{m}{n}$ is the number of carries when $n$ and $m-n$ are added in base $p$. Is that "non-simple"? – Arturo Magidin Oct 19 '11 at 18:35
If $r=10$, $k=7$, then $0\lt k\leq 2^{8}$, $2^{10}$ certainly divides $\binom{2^{r-2}}{k}2^{14}$, but it also divides $\binom{2^{10-\ell}}{7}2^{14}$ for any $\ell\gt 2$ (since it is always a multiple of $2^{14}$. Or did I misinterpret your phrasing? – Arturo Magidin Oct 19 '11 at 19:21
up vote 2 down vote accepted

I don't know off-hand about the binomial coefficients, but here's a proof of the order of $5$.

For $r=3$, the order of $5$ is $2$, which agrees with what we want. So assume that $r\gt 3$.

Assume that the order of $5$ has order $2^{r-2}$ modulo $2^{r}$. The order of $5$ modulo $2^{r+1}$ is a multiple of $2^{r-2}$. It cannot be of order $2^r$ (the order of the group), because both $2^{r}-1$ and $2^r+1$ have order $2$ and they are not congruent modulo $2^{r+1}$ so the group of units is not cyclic. So the order of $5$ is either $2^{r-2}$ or $2^{r-1}$.

Since the order of $5$ modulo $2^{r}$ is $2^{r-2}$, and the order modulo $2^{r-1}$ is $2^{r-3}$, then $5^{2^{r-3}}\equiv 1 \pmod{2^{r-1}}$, so $5^{2^{r-3}}\equiv 1 + k2^{r-1}\pmod{2^{r}}$, with $k=0,1$. Can't be $k=0$, because then the order of $5$ modulo $2^r$ would divide $2^{r-3}$, so $5^{2^{r-3}}\equiv 1 + 2^{r-1}\pmod{2^r}$. Hence $5^{2^{r-3}}\equiv 1 + 2^{r-1} + k2^r\pmod{2^{r+1}}$, with $k=0$ or $1$. Squaring both sides, we have: $$\begin{align*} 5^{2^{r-2}} &\equiv (1 + 2^{r-1} + k2^r)^2\pmod{2^{r+1}}\\ &\equiv 1 + 2^{2r-2} + k2^{2r} + 2^r + k2^{r+1} + k2^{2r}\pmod{2^{r+1}}\\ &\equiv 1+2^r\pmod{2^{r+1}}. \end{align*}$$ So the order of $5$ is $2^{r-1}$, as desired.

share|cite|improve this answer
You are amazing, this proof is not easy to come up with :-) – Manos Oct 19 '11 at 20:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.