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!

  • $\begingroup$ Why should $p \mid 2(n-1)$ and $p \nmid n - 1$ imply $p \mid 2$? $\endgroup$ – Mr. Chip Aug 7 '16 at 12:08
  • $\begingroup$ @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$. $\endgroup$ – Weijie Chen Aug 7 '16 at 12:19
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Aug 7 '16 at 12:20
  • 1
    $\begingroup$ Why should the order be prime? The order of 2 mod 5 is 4, which isn't prime. $\endgroup$ – Dylan Aug 7 '16 at 14:24
  • 1

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.

  • $\begingroup$ Why $q\equiv 1$ $mod$ $2^s$? it is clear that every prime is $q\equiv 1$ $mod$ $4$. $\endgroup$ – Weijie Chen Aug 9 '16 at 12:43
  • $\begingroup$ 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$. $\endgroup$ – Dylan Aug 9 '16 at 12:50
  • $\begingroup$ 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)} $$ $\endgroup$ – Weijie Chen Aug 9 '16 at 12:55
  • $\begingroup$ $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$. $\endgroup$ – Dylan Aug 9 '16 at 12:58
  • $\begingroup$ Finally the last two staments why does the first implies the second one? $\endgroup$ – Weijie Chen Aug 9 '16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.