Divisibility Of $(2^{32} +1)$

Question

Here is my problem: If $2^{32} +1 $ is completely divisible by a whole number. Which of the following numbers is completely divisible by that number :
(A)($2^{16}+1$)
(B)($2^{16}-1$)
(C)$7*2^{23}$
(D)($2^{96}+1$)

I don't know where to start any help is appreciated.
Thank you

Answer 1

Hint 1: We want to find an option that is divisible by $2^{32} + 1$. Indeed, this is necessary and sufficient: it is necessary since we can choose $2^{32} + 1$ as the factor that divides $2^{32} + 1$ and it is sufficient since if a number is divisible by $r = de$, then it is divisible by $d$ and $e$ as well.

Hint 2: $a^3 + 1 = (a + 1)(a^2 - a + 1)$.

---

These hints tell us that (d) is the right answer, since $$2^{96} + 1 = (2^{32})^3 + 1 = (2^{32} + 1)(2^{64} - 2^{32} + 1),$$ so $2^{32}+1 \mid 2^{96} + 1$.

We can also rule out the others if we are not given that there are multiple answers: (a) (b) and (c) are all less than $2^{32} + 1$, so $2^{32} + 1$ cannot divide all of them evenly. We may even show that they share no common factors with $2^{32} + 1$ at all.

(a) and (b) are out since their product is $2^{32} - 1$. The only common divisor of $2^{32} - 1$ and $2^{32} + 1$ could be $2$ since their difference is $2$, but they're both odd so $\gcd (2^{32} + 1, 2^{32} - 1) = \gcd(2^{32} + 1, 2^{16} - 1) = \gcd(2^{32} + 1, 2^{16} + 1) = 1$.

(c) can be ruled out since its only divisors are $2$ and $7$. $2$ is not a divisor of $2^{32} + 1$ since it is odd, $7$ is not a divisor since $2^3 \equiv 1 \pmod 7$ and so $2^{32} + 1 \equiv 2^2 (2^3)^{10} +1 1 \equiv 4 + 1 \equiv 5 \pmod 7$.

Answer 2

Hint 3: What is the product of (A) and (B)?

Hint 4: $2^n \space \text{mod} \space 7$ can only be $1$, $2$, or $4$.

Answer 3

Another way to do this would be to realise that any number which is not co-prime to $2^{32}+1$ is an answer (provided that it is in the options). The converse is also true.

So, we check which of the following $gcd(2^{32}+1, 2^{16}+1)$, $gcd(2^{32}+1, 2^{16}-1)$, $gcd(2^{32}+1, 7 \times 2^{23})$, $gcd(2^{32}+1, 2^{96}+1)$ is not 1. This is easy to do using euclidean algorithm even if we don't use properties of Fermat numbers,etc.

$gcd(2^{32}+1, 2^{16}-1)=gcd(2^{32}+1-2^{32}+2^{16},2^{16}-1)=gcd(2^{16}+1,2^{16}-1)=1$ similarly for others.

We find among the options that only $2^{96}+1$ is not co-prime to $2^{32}+1$