Power Primes!

Since $2^{q-p}-1$ is odd, p and q must each be odd primes. Also, since $pq \leq 1000$ and $p < q$ , we have $p \leq 31$ . Therefore, p = 3, 5, 7, 11, 13, 17, 19, 23, 29, or 31.

Thinking in terms of modular arithmetic, we have $2^{q-p} \equiv 1 \pmod{ pq}$ . Since p and q are relatively prime, this means $2^{q-p} \equiv 1 \bmod p$ and $2^{q-p} \equiv 1 \bmod q$ .

$2^{q-p} \equiv 1 \bmod p$ implies that $2^q \equiv 2^p \bmod p$ . By Fermat's Little Theorem, $2^p \equiv 2 \bmod p$ . This means that $2^{q-1} \equiv 1 \bmod p$ . But since, $2^{p-1} \equiv 1 \bmod p$ and p < q, we must have $p-1 | q-1$ .

Likewise, we find that $2^{p-1} \equiv 1 \bmod q$ . This is a much more restrictive condition.

Consider each case for p:

If p = 31, then since pq < 1000 we must have q = 31, which contradicts p < q.

If p = 29, then p-1=28 and there are no primes q for which $p-1 | q-1$ and $pq < 1000$ . The same is true for p = 23 and 17.

If p = 19, then p-1=18 and the only prime q for which $p-1 | q-1$ and $pq < 1000$ is q = 37.

If p = 13, then p-1 = 12 and the only primes q for which $p-1 | q-1$ and $pq < 1000$ are q = 61 and 73.

If p = 11, then p-1 = 10 and the only primes q for which $p-1 | q-1$ and $pq < 1000$ are q = 31, 41, 61, and 71.

If p = 7, then p-1 = 6 and there are no primes q for which $p-1 | q-1$ and $pq < 1000$ . The same is true for p = 5 and 3.

So our possible candidates for solutions are (p,q) = (19,37), (13, 61), (13, 73), (11, 31), (11, 41), (11, 61), and (11, 71). We now check to see for which candidates $2^{p-1} \equiv 1 \bmod q$ .

Using the repeated squaring technique to compute each situation, we find that only $2^10 \equiv 1 \bmod 31$ . So the only solution is p = 11, q = 31, which gives N = 341.

A number N=p*q, where p and q are different primes is calles a pseudoprime to base a if a^{N-1} \equiv 0 \pmod N. For obvious reasons p cannot be 2, hence N has to be odd. N also sastisfies 2^q \equiv 2^p \pmod N which simplifies to 2^{N} \equiv \pmod N. Only primes and pseudoprimes sastify the last equation, since we look for nonprimes we have to look at all pseudoprimes smaller or equal to 1000 with 2 factors. This criteria only sastifies 341.

q>p therefore p<31. 2^(q-1)-1 divide by q and 2^(q-p) - 1 divide by q, therefore 2^(p-1)-1 divide by q. 2^(p-1)-1 also divide by p, so 2^(p-1)-1 divides by N. choose p is prime from 3 to 29, and find q. there is only p=11, q=31 is satisfied. Then, N= 341.

We denote the greatest common divisor of $n$ and $m$ by $\gcd(n,m).$

By the Fermat's theorem, $2^{p-1}\equiv 1 \pmod p.$ Because $2^{q-p}\equiv 1 \pmod p,$ this implies that $2^{q-1} \equiv 1 \pmod p.$ Also, by Fermat's theorem $2^{q-1} \equiv 1 \pmod q$ . Finally, $2^{p-1} = 2^{q-1}/2^{q-p} \equiv 1 \pmod q$ . So $pq$ divides $\gcd(2^{p-1}-1,2^{q-1}-1)$ .

The following lemma is very useful.

Lemma. For any integer $k\geq 2$ , and positive integers $n$ and $m$ , $\gcd(k^n-1,k^m-1)=k^{\gcd(n,m)}-1$ Proof. Suppose $n<m$ . We note that $\gcd(k^n-1,k^m-1)=\gcd(k^n-1, (k^n-1)\cdot k^{m-n}+(k^{m-n}-1))=\gcd(k^{n}-1,k^{m-n}-1)$ So we can run Euclid's algorithm (with subtraction steps) on the numbers of the form $k^i-1$ parallel to the same algorithm for the powers $i$ . The result follows.

Applying this lemma to $2^{p-1}-1$ and $2^{q-1}-1,$ we get that for $d=\gcd(p-1,q-1)$ the following are true: $pq \mid 2^d-1,\ d\mid (p-1),\ d\mid (q-1)$ .

Because $p<q$ and $pq<1000,$ one can see that $p\leq 29.$ We will consider several cases, based on what $p$ can be. Note that $p\neq 2.$

If $p=3,$ then $d\mid 2$ . Both $2^{1}-1=1$ and $2^2-1 =3$ are not divisible by a pair of distinct primes, so this is impossible.

If $p=5,$ then $d\mid 4.$ The above calculations show that $d=1, 2$ are not suitable, so we only need to check $d=4.$ Then $2^d-1 =3\cdot 5,$ so we have no candidate for $q$ .

If $p=7,$ then $d\mid 6$ . If $d=3$ , then $2^d-1=7,$ and if $d=6,$ then $2^d-1=63=3^2\cdot 7.$ Neither works.

If $p=11,$ then $d\mid 10$ . If $d=5,$ then $2^d-1=31,$ which is not divisible by $p.$ If $d=10,$ then $2^d-1=1023=3\cdot 11\cdot 31.$ Note that $p=11$ and $q=31$ work, which gives $N=341$ .

If $p=13,$ then $d\mid 12$ . The above calculations show that $d=1, 2, 3, 4, 6$ do not yield solutions, so we only need to consider $d =12$ . Since $2^{12}-1=(2^6-1)(2^6+1)=3^2\cdot 5\cdot 7 \cdot 13,$ so it does not work.

If $p=17,$ then $d \mid 16$ . The above calculations show that $d = 1, 2, 4$ do not yield solutions, so we should check $d=8$ and $d=16$ . If $d=8$ , then $2^8-1=255 = 3 \cdot 5 \cdot 17$ , which doesn't yield a valid $q$ . If $d=16,$ then $2^{16}-1=(2^8-1)(2^8+1)=255\cdot 257=3\cdot 5 \cdot 17\cdot 257.$ But $17 \times 257 > 1000$ , hence this has no solutions.

If $p=19,$ then $d \mid 18$ and $q< \frac{1000}{p}<53$ . The above calculations show that $d=1, 2, 3, 6$ do not yield solutions, so we should check $d=9$ and $d=18$ . If $d=9,$ then $2^9-1=511=7\cdot 73.$ This does not work because $19 \times 73>1000$ . If $d=18,$ then $2^{18-1}=511\cdot 513=(7\cdot 73)\cdot(3^3\cdot 19)$ , which likewise has no solutions.

If $p=23,$ then $d=11$ or $d=22$ . In both cases, $22|(q-1),$ so the smallest $q$ could be is $67$ . But $22\cdot 67>1000$ .

If $p=29$ , then $d$ must be a multiple of $7$ , so the smallest $q$ could be is $43,$ which is too big.

So, the only such number $N$ up to $1000$ is $341$ , and the answer is $341.$

Iterate over all pairs of primes (p,q) such that n=p*q<=1000 To check whether N divides 2^{q-p} - 1 we can see that 2^{q-p} - 1 is sum of 2^k where k is from 0 to q-p-1. Therefore we can calculate S which is sum of (2^k) mod N. If S mod N = 0 then N divides S, then we add N to the result X. Finally the result is the 3 last digits of X.