How Many Dividing Pairs?

Note that if $i$ is a divisor of $2^j - 1$ , we have: $2^j - 1 \equiv 0 \pmod{i}$

Another thing to note: $2^j-1 \equiv -1 \equiv 1 \pmod{2}$

Hence, $2^j-1$ is odd which implies $i$ to be odd...

When I saw an expression of the form $~a^n-1\equiv 0 \pmod{N}$ , two things went on my mind: Fermat's Little Theorem and Euler's Theorem ..

Fermat's Little Theorem : If $a$ is an integer and $p$ is a prime, then...

$a^{p-1}-1 \equiv 0 \pmod{p}$

We can use $a=2$ and $p=i$ ... But this gives only the values of $i$ when $i$ is a prime... So we need a more generalized version...

Euler's Theorem : If $n$ and $a$ are positive integers and they are coprime, then...

$a^{\varphi(n)}-1\equiv 0 \pmod{n}$

Now we have something useful... We can set $a=2$ and $n=i$ and get...

$2^{\varphi(i)}-1\equiv \pmod{i}$

And hence, we can set $j=\varphi(i)$ (Note that $i$ is odd and $2$ is even and also a prime, and so they are obviously coprime)... By the definition of Euler's totient function and according to the question and our assumption, we have...

$1\le \varphi(i)=j\le i\le 1000$

So we're done... Don't forget that $i$ is odd... Hence for all such odd $i$ , there exists a $j$ , such that...

$2^j-1\equiv 0 \pmod{i}$

All that's left is counting the number of odd integers in the interval $[1,1000]$ which is simply...

$\dfrac{1000}{2}=\fbox{500}$

Note : This solution could be shortened further to only 4-5 lines... But I tried to illustrate every step I took such that the beginners like me can easily understand... :) Thanks!

First of all, note that $i$ must be odd, since otherwise we get that an even number divides an odd number. We claim that all odd values of $i$ work, and thus the answer is $\boxed{500}$ .

Consider the set $\{2^1,2^2,2^3,\cdots,2^{1000}\}$ . By the Pigeonhole principle, there must be two elements that have the same residue modulo $i$ , since $i\le 999$ and has at most 999 residue classes. Let these two elements be $2^a$ and $2^b$ , with $a>b$ . Then, since 2 and $i$ are coprime, $2^a\equiv 2^b\pmod i\implies 2^{a-b}\equiv 1\pmod i$ Since $a\le 1000$ and $b\ge 1$ , $a-b\le 999$ , and so $j=a-b$ must satisfy $i|2^j-1$ and $1\le j\le 1000$ . We conclude that a $j$ exists for all $\boxed{500}$ odd $i$ .

Motivation: First, I eliminated even numbers, and then I suspected that all odd numbers, or maybe all but a couple, like 999, worked. The proof followed relatively quickly when I thought about the different possible remainders.

It is clear that $i$ must be odd; otherwise it is impossible for $2^{j}-1,$ an always odd number, to be a multiple of $i.$ So, assume that $i$ is odd. We can rewrite the given equation using modular arithmetic to get $2^j \equiv 1 \pmod i.$ By Euler's Theorem, $2^{\phi(i)} \equiv 1 \pmod i,$ where $\phi(i)$ is the Euler function; then since $\phi(i) \le i$ and $i \le 1000$ for all $i,$ we can choose $j = \phi(i)$ for all $i,$ implying that all odd $i$ work. Thus, the possible $i$ are precisely the odd numbers in the range $1, 2, \ldots, 1000,$ of which there are $\boxed{500}.$

Clearly, there are a lot of options for $i$ and $j$ so we really want to limit our options. When we see the word divisor , it is quite motivated to think about parity , in other words, odd and even factors. Also, we see $2^j - 1$ which is a power , and we can change the problem to one regarding $\pmod i$ , so it would be motivated to consider (the generalised form of Fermat's Little Theorem) Euler's theorem which, by the way, says that: For $a$ relatively prime to $m$ , we have

$a^\phi(m) \equiv 1 \pmod m$ .

---

So since $i$ is a divisor, it would be a neat idea to do some analysis of $i$ first. Since $2^j - 1$ is odd, $i$ must be odd too (and not even).

So turning to our second idea, for odd $i$ , let $j = \phi(i)$ to get by Euler's theorem, $2^\phi(i) - 1 \equiv 0 \pmod i$ . Here's the catch, notice that since $i < 1000$ , by definition, $\phi(i) < 1000$ , so for every odd $i$ we can find a matching $j$ .

Lastly, just remember that there are $\frac{1000}{2} = \fbox{500}$ odd $i$ that is less than $1000$ .

• Please correct my solution if there are any shortcomings in the solution.

2^j - 1 is always an odd number. By Fermat's Little Theorem, 2^j is congruent to 1 (modulo p). We can say that j = p - 1. 2^(p-1) is congruent to 1 modulo p. For any odd p, this condition satisfies. How about the composite odd numbers? By the theorem again, the gcd of 2 and any odd p is always 1. Hence, there 500 odd numbers that satisfies this condition.

If $i$ is even, then $n\nmid2^j-1$ since $2\nmid2^j-1$ . Otherwise, $i$ is odd and so $\gcd(2,i)=1$ , hence $i\mid2^{\phi(n)}-1$ . Since $\phi(n)\le n-1$ , it holds for all odd $i$ , which are $500$ $i$ 's in total on this interval.

by Fermat's little theorem a^{p-1} -1 is divisible by p if p and a are coprime. All odd numbers are coprime to 2,hence all odd numbers are divisible by 2^{j} -1