Certain properties of numbers such that $n \mid 2^n+1$ A natural number $n>1$ is called good if$$n \mid 2^n+1.$$ For example, $n=3$ is good, as $3 \mid 2^3+1=9$. Prove that if $N_1$ and $N_2$ are good, then:


*

*$\mathrm{lcm}(N_1,N_2)$ and $\gcd(N_1,N_2)$ are good,

*$N_1\cdot N_2$ is good. 


This seems pretty difficult for me. Any hints?

You can prove "good" ness pretty easily without knowing much more about $N_1 $ and $N_2$, but I thought I'd share the properties that make numbers "good", and thus you can see that your problem becomes trivial.
We are going to go case by case where we assume something about $n$, take it to its conclusion, and then sew together the cases to get the overall answer.
Case 1: n is 1
1 divides every integer, and  21+1=3  is an integer. n = 1 is part of the solution set.
Case 2: n is even
If $n$ is even, every multiple of $n$ must also be even. But $2^n + 1$ is clearly odd, so no even $n$ will divide it. So $n$ cannot be even.
Case 3: If n is a power of an odd prime
Let $n=p^k$ where p is an odd prime. If $n$ divides $2^n + 1$, so does $p$
$2^n+1=2^{p^k} + 1 = 2^{p^{k-1}*p} + 1 = (2^{p^{k-1}})^p + 1$
$2^{p^{k-1}$ is relatively prime to $p$ (hint, both $p$ and $2$ are primes). Let $2^{p^{k-1}}$ = a
By Fermat's Little Theorem, we know that $a^p \equiv a\mod p$
So, $(2^{p^{k-1}})^p + 1 \equiv 2^{p^{k-1}} + 1\mod p)$
We can keep reducing this modulo $p$ and reducing the powers of $p$ in the exponent until we have only 1, so we get $2^p + 1 \equiv 2 + 1 \equiv 3\mod p$
This means that $2^n + 1 \equiv 3\mod p$ . But $p$ divides $2^n + 1$, so $p$ must divide 3 as well, i.e. $p = 3$
So if n is the power of an odd prime, it must be a power of 3.
Does this mean that all powers of 3 satisfy our condition? We don’t know yet. We are currently only gathering “necessary” conditions, not “sufficient”.
Case 4: If n is a product of powers of distinct odd primes
This is the last and most general case, as all odd numbers are a products of powers of odd primes. If $n$ is a product of prime powers, then let $p$ be least such prime that divides $n$.
Let $n = mp^k$ , where $m$ is a product of powers of primes larger than $p$, and $k$ is some integer.
Similar to case 3, we can see that $2^n + 1 = 2^{mp^k} + 1 = (2^{mp^{k-1}})^p + 1 \equiv 2^{mp^{k-1}} + 1\mod p$
We can keep reducing this modulo $p$ and pick off powers of p until we get $2^m + 1$
We have thus shown that if $p$ divides $2^n + 1$, it then divides $2^m + 1$
$2^m \equiv -1\mod p$, so $2^{2m} \equiv 1\mod p$ so $4^m \equiv 1\mod p$
Let $q$ be the order of $4\mod p$ (i.e. the lowest integer satisfying $4^q \equiv 1\mod p$). We know 4 has an order as it is relatively prime to any odd prime. We know $q$ divides $m$ as that’s a property of the order.
Also, as $q$ is the order of $4$ mod $p$ , $q$ must also divide $\phi(p)$, i.e. $q$ must also divide $p - 1$.
However, $q$ is clearly larger than $p - 1$ . $q$ is a divisor of $m$, and all divisors of $m$ are at least as big as their prime factors, all of which are larger than $p$ by design.. So $q$ cannot divide $p - 1$. This gives us our coveted contradiction.
So n cannot be a product of powers of distinct odd primes.
Cases 2 and 4 are eliminated.
So we are left with two cases

*

*$n = 1 $

*$n = 3^k$ for some integer $k$
This is really just one case ($3^0 = 1$), but we’ll get to that later. These $3^k$ powers are just candidates.
How do we prove that every power $3^k$ divides $2^{3^k} + 1$ ?
We can try proving this by induction. We know that for $k = 1$, $2^3 + 1 = 9$ which is divisible by $3^1$.
Let $2^{3^k} + 1 = a*3^k$, $a,k \in N $
All these exponents can make one feel wonky, but we can observe that $2^{3^k}$ can be turned into $2^{3^{k+1}}$ by cubing.
So cubing both sides, we get:
$2^{(3^k)(3)} + 3*2^{(3^k)(2)} + 3*2^{3^k} + 1 = (a^3)(3^{3k})$
$2^{3^{k+1}} + 1 = (a^3)(3^{3k}) - 3*2^{3^k}(2^{3^k} + 1) $
We know that $3^{3k}$ is clearly divisible by $3^{k+1}$ as $3k > k + 1$.
So let $(a^3)(3^{3k}) = b.3^{k+1}$
$2^{3^{k+1}} + 1 = b.3^{k+1} - 2^{3^k}*3*a*3^k$
$2^{3^{k+1}} + 1 = b.3^{k+1} - 2^{3^k}*a*3^{k+1}$
The RHS is clearly divisible by $3^{k+1}$, so we have our proof.
The answer is: all numbers $n=3^k$ where $k \geq 0$ satisfy the property “$n$ divides $2^n + 1$”
From this point, proving your statements about good numbers is trivial.
