# Find all positive integers $n$ such that $\frac{2^{n-1}+1}{n}$ is integer. Where I'm wrong?

The problem statement is: Find all positive integers $n$ such that $\frac{2^{n-1}+1}{n}$ is integer.

Source: LTE Amir Houssein Pavardi P.25

My approach:

It is clear that $n=1$ is a solution, so supose that $n>1$.

$2^{n-1}\equiv -1$ $mod$ $n$;

$2^{2(n-1)}\equiv 1$ $mod$ $n$;

Observe that $n$ is odd hence $n-1$ is even. But if $p=ord_n(2)$ then $p|2(n-1)$ but not $(n-1)$ so $p|2$ how ever it is a contradiction because $n-1$ is even. So the unique solution is $n=1$

Is this proof correct? Because I'm not sure if order properties does apply to composite modulo. And if anyone has a solution involving LTE trick please post a partial proof Thanks in advance!

• Why should $p \mid 2(n-1)$ and $p \nmid n - 1$ imply $p \mid 2$? – Mr. Chip Aug 7 '16 at 12:08
• @JoshuaCiappara By orders properties (at least for prime modulo, that's why I asked) because if $a^d\equiv 1$ $mod$ $n$ if and only if $ord_n(a)\mid d$. It can be seen with the property that $gcd(a^b-1,a^d-1)=a^{gcd(b,d)}-1$. – Weijie Chen Aug 7 '16 at 12:19
• Are you assuming $\mathrm{ord}_n(2)$ is prime, perhaps? $6\mid 2\cdot 9$ but it is not true that $6\mid 9$. Still, it is also not true that $6\mid 2$. – Thomas Andrews Aug 7 '16 at 12:20
• Why should the order be prime? The order of 2 mod 5 is 4, which isn't prime. – Dylan Aug 7 '16 at 14:24
• – lab bhattacharjee Aug 7 '16 at 15:08

## 1 Answer

It is clear that $n$ must be odd, and hence every prime factor of $n$ is odd. Suppose that $n \neq 1$. Then $n$ has some odd prime factor.

Of all of the prime factors of $n$, let $p$ be the one for which the maximum power of $2$ which divides $p - 1$ is smallest.

Then we can write $p = 2^s \cdot t + 1$ for some $s > 0$ and odd natural number $t$. By the way we chose $p$, we have that for any prime factor $q$ of $n$ that $q \equiv 1 \pmod{2^s}$, and hence that $n \equiv 1 \pmod{2^s}$.

Thus we can write $n = 2^s \cdot \alpha + 1$ for some natural number $\alpha$. Let $g$ be a primitive root modulo $p$. Then there is some natural number $\beta$ such that $g^\beta \equiv 2 \pmod p$. Now we know that $$p \,\mid\, n \,\mid\, 2^{n-1} + 1$$ and so $$g^{\beta(n-1)} \equiv 2^{n-1} \equiv -1 \equiv g^{(p-1)/2} \pmod p.$$

It follows that $$2^s \alpha \beta \equiv \beta(n - 1) \equiv \frac{p-1}{2} \equiv 2^{s-1} t \pmod{(p-1)}$$ and so $$2^s \alpha \beta \equiv 2^{s - 1} t \pmod{2^s t}$$ which implies that $$0 \equiv 2^{s - 1} t \pmod{2^s}$$ which is a contradiction since $t$ is odd.

• Why $q\equiv 1$ $mod$ $2^s$? it is clear that every prime is $q\equiv 1$ $mod$ $4$. – Weijie Chen Aug 9 '16 at 12:43
• For every prime $q$ which divides $n$, there is a largest power of $2$ which divides $q - 1$. We choose $p$ to be the prime for which that power of $2$ is the smallest. So $p - 1$ is divisible by $2^s$, and for every other prime $q$, the largest power of $2$ which divides $q - 1$ is at least $2^s$. So the claim that every $q$ satisfies $q \equiv 1 \pmod{2^s}$ follows from how we choose $p$. Alternatively, you could define $s$ to the largest natural number such that $q \equiv 1 \pmod{2^s}$ for every prime $q$ which divides $n$. – Dylan Aug 9 '16 at 12:50
• Ok, and last thing can you explain me why? $$2^s \alpha \beta \equiv \beta(n - 1) \equiv \frac{p-1}{2} \equiv 2^{s-1} t \pmod{(p-1)}$$ – Weijie Chen Aug 9 '16 at 12:55
• $g$ is an element of order $p - 1$. (Such an element exists for every prime $p$.) This means that since $g^{\beta (n - 1)} \equiv g^{(p-1)/2}$ that $\beta (n - 1) - (p - 1)/2$ must be divisible by $p - 1$ since $g^{\beta(n - 1) - (p-1)/2} \equiv 1 \pmod p$. But we also have that $\beta (n - 1) = 2^s \alpha \beta$ and that $(p - 1)/2 = 2^{s - 1} t$. – Dylan Aug 9 '16 at 12:58
• Finally the last two staments why does the first implies the second one? – Weijie Chen Aug 9 '16 at 13:04