1
$\begingroup$

Find $n$ such that $n$ divides $2^n + 2$. Also, $n$ should be between $100$ and $1000$.

It can be easily seen that $n$ is not a multiple of $4$. By brute force I have figured out that answer is $946$, but I don't know how to proceed further.

$\endgroup$

1 Answer 1

3
$\begingroup$

See OEIS sequence A006517 and references there.

EDIT: $n$ must be even, but not divisible by $4$, and it's not hard to show that $n=2p^j$ for prime $p$ doesn't work, so $n$ is divisible by at least two odd primes. Let's say we guess that $n = 2 p q$ for odd primes $p < q$. Since $n/2 < 500 < 23^2$, we must have $p < 23$. Thus we need $ 2^{2pq-1} + 1$ to be divisible by $p$ and by $q$. By Fermat's Little Theorem, $2^{2pq} \equiv 2^{2q} \mod p$, so $p | 2^{2q-1}+1$ and $q | 2^{2p-1} + 1$. Try each possible $p$ in turn.

For $p = 3$, $2^{2p-1} + 1 = 33$ so $q = 11$: too small ($2pq = 66 < 100$).

For $p = 5$, $2^{2p-1} + 1 = 513 = 3^3 \times 19$ so $q = 19$, but $2^{2q-1} \equiv (-1)^q \times 2^{-1} \equiv 2 \mod 5$, no good.

For $p = 7$, $2^{2p-1} + 1 = 8193 = 3 \times 2731$ so $q = 2731$, too big.

For $p = 11$, $2^{2p-1} + 1 = 2097153 = 3^2 \times 43 \times 5419$, so $q = 43$. And $2^{2q-1} + 1 = 2^{85} + 1 \equiv 2^5 +1 \equiv 0 \mod 11$, so this one works: $n = 2 \times 11 \times 43 = 946$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .