Let $a>1$ be an odd positive integer. Find the least positive integer $n$ such that $2^{2000}$ is a divisor of $a^n-1$. Mircea Becheanu
Problem
Source: Romanian TST 2000
Tags: modular arithmetic, number theory proposed, number theory
Rust
18.02.2011 17:52
Let $n_1=v_2(a-1),n_2=v_2(a+1)$. Jbviosly one of them 1. If $n_1\ge 2000$, then $n=1$. Else consider $n_1+n_2$. If $n_1+n_2\ge 2000$, then $n=2$. Else $n=2^{2000-n_1-n_2+1}.$
WakeUp
18.02.2011 18:25
This is a nice problem imo, so I can't resist posting a solution We need $a^n=1\pmod{2^{2000}}$. And so we are looking for the order of $a$ modulo $2^{2000}$. Now by Euler's theorem $n|\varphi (2^{2000})=2^{1999}$ and hence it is a power of $2$. Let $n=2^k$ where $k\ge 0$. Then : \begin{align*} a^n-1 & =a^{2^k}-1\\ & =(a^{2^{k-1}}-1)(a^{2^{k-1}}+1)\\ &= (a^{2^{k-2}}-1)(a^{2^{k-2}}+1)(a^{2^{k+1}}+1)\\ & \ldots \\ & =(a-1)(a+1)(a^2+1)(a^4+1)\cdots (a^{2^{k-1}}+1)\end{align*} But $a^{2m}+1=2\pmod{4}$ hence $2^{k-1}||(a^2+1)(a^4+1)\cdots (a^{2^{k-1}}+1)$. Since we require $2^{2000}|a^n-1$, we need $2^{2001-k}|(a-1)(a+1)$. Of course either $2||a-1$ or $2||a+1$. Denote, as Rust, the positive $n_1=v_2(a-1),n_2=v_2(a+1)$ as the highest exponent of $2$ dividing $a-1,a+1$ respectively. This means $2^{n_1+n_2}||(a-1)(a+1)$ and so $2001-k\le n_1+n_2$, or $2001-n_1-n_2\le k$. This leads to the answer: \[k=\begin{cases}0, & \text{if }2001-n_1-n_2\le 0\\ 2001-n_1-n_2, & \text{if }2001-n_1-n_2>0\end{cases} \] i.e. $n=1$ for $2001-n_1-n_2\le 0$ and $n=2^{2001-n_1-n_2}$ when $2001-n_1-n_2>0$. We can actually afford to be a bit more specific. Of course one of $n_1,n_2$ is equal to $1$. The other is either larger than $2000$ or not...
vladimir92
19.02.2011 03:31
If I'm not wrong, My Idea is similar to the previous one.
It's obvious that there exist a non negative integer $k$ so that $n=2^k$, define the two sequence, $(M_i)_{i\geq0}$ and $(L_i)_{i\geq0}$ by: $M_i=a^{2^i}-1$ and $L_i=v_2(M_i)$, and put $n_1=v_2(a+1)$ , and $n_2=v_2(a-1)$.
We know that a number of the forme $x^2+1$ can never be a multiple of $4$, therefor, for every integer $i\geq 1$: $L_{i+1}=v_2(M_{i+1})=v_2(M_i)+1=L_i+1$ solving the last relation, we get that $L_i=i-1+L_1$ for every $i\geq 1$. Now we are searching for the smallest $k$ for which $L_k\geq 2000$ and from the previous fact we get two possiblities.
\[ k=\begin{cases}0, &\text{if }2^{2000}|a-1\\ 2001-n_{1}-n_{2}, &\text{else }\end{cases} \]
Takeya.O
08.09.2016 15:16
Case1:$v_2(a-1)\ge 2000$ $n=1$ satisfies the condition. Case2:$1\le v_2(a-1)\le 1999$ If $n$ is odd, $v_2(a^n-1)=v_2(a-1)+v_2(a^{n-1}+\dots +1)=v_2(a-1)$.Thus $n$ is even.By LTE, $v_2(a^n-1)=v_2(a-1)+v_2(a+1)+v_2(n)-1\ge 2000$ Case2-1:$2\le v_2(a-1)\le 1999$ Since $v_2(a+1)=1$, $v_2(n)\ge 2001-v_2(a-1)-v_2(a+1)>0$. Case2-2:$v_2(a-1)=1$ If $v_2(a+1)\ge 1999$,$n=2$ satisfies the condition.Else $v_2(n)\ge 2001-v_2(a-1)-v_2(a+1)$ Therefore \[ n=\begin{cases}1 &\text{if }v_2(a-1)\ge 2000\\ 2 &\text{else if }v_2(a-1)+v_2(a+1)\ge 2001\\ 2^{2001-v_2(a-1)-v_2(a+1)} &\text{else if }v_2(a-1)+v_2(a+1)\le 2000\end{cases} \]