Let $d = gcd(n, 2^n - 1)$ and $p$ the least prime divisor of $d$. So, $2^n \equiv 1 (mod$ $p)$ $\Longrightarrow ord_{p}(2) \mid n$ and $ord_{p}(2) \mid p - 1$ by FLT, then $p > ord_{p}(2)$ $\Longrightarrow ord_{p}(2) = 1$ $\Longrightarrow p = 1$ $ABS!$ Thus, $gcd(n, 2^n - 1) = 1$ $\Longrightarrow 2^n - 1$ is a perfect square then if $n \geq 2$ it's false mod $4$. Therefore, only $n = 1$ is sol.

Marcos_Vinicius wrote: Let $d = gcd(n, 2^n - 1)$ and $p$ the least prime divisor of $d$. So, $2^n \equiv 1 (mod$ $p)$ $\Longrightarrow ord_{p}(2) \mid n$ and $ord_{p}(2) \mid p - 1$ by FLT, then $p > ord_{p}(2)$ $\Longrightarrow ord_{p}(2) = 1$ $\Longrightarrow p = 1$ $ABS!$ Thus, $gcd(n, 2^n - 1) = 1$ $\Longrightarrow 2^n - 1$ is a perfect square then if $n \geq 2$ it's false mod $4$. Therefore, only $n = 1$ is sol. I think $p>ord _p(2)$ doesn't mean that $ord _p(2)=1$ (since the least prime divisor of $d$ is not the least prime divisor of $n$) So $\gcd(n,2^n-1)$ may greater than $1$ ($n=21$)

Hint: considere p : the greatest prime divisor of n

And get a contradiction by mod 4 so the only solution is when n does not have any prime divisor (n=1)

Again, we devour this with Quadratic Reciprocity and Residues (I will provide a basic outline here.) Lemma 1 : There are quadratic non residues for any moduli $m$ except when $m=1$ or $m=2$. Basically this confirms the existence of some $a$ such that $gcd(a,m)=1$ and $\not\exists \ x : x^2 \equiv a \ (mod \ m)$. It is well known that when $p \ge 3$ there are $\frac{p-1}{2}$ non residues. So by C.R.T we can create quadratic non residues modulo $m$. This can be more rigorously and formally proven through basic group theory. Note that if $n(2^n-1)=k^2$ for some $k$. Then, $n(2^n-1)$ is a quadratic residue modulo any prime $p$. We construct a $p$ so that this fails. Case 1 (n is odd): We define $t \coloneq gcd(n,2^n-1)$ and consider the solution to $p \equiv 1 \ (mod \ 4)$, $p \equiv 1 \ (mod \ \frac{n}{t})$ and $p \equiv j \ (mod \ \frac{2^n-1}{t})$ such that $j$ is quadratic non residue of $\frac{2^n-1}{t}$ exists by Lemma 1. Notice that since $gcd(\frac{n}{t},\frac{2^n-1}{t})=1$ there exists a solution by C.R.T and then finally, $gcd(4,\frac{n(2^n-1)}{t^2})=1$ so there is an A.P satisfying the following conditions such that it is prime (by dirichlet). Also $gcd(p,n)=gcd(2^n-1,p)=1$ obviously due to the construction. Secondly dirichlet follows since all the congruences are in coprime moduli, so the resulting moduli will also be coprime (trivial lemma). Now introduce jacobi symbol and due to quadratic reciprocity and construction, $1=(\frac{p}{\frac{n}{t}})=(\frac{\frac{n}{t}}{p})$ and $(-1)=(\frac{p}{\frac{2^n-1}{t}})=(\frac{\frac{2^n-1}{t}}{p})$. The last fact follows by construction. Notice also that, $gcd(t,p)=gcd(t^2,p)=1$ and therefore, $(\frac{t^2}{p})=1$. Due to complete multiplicativity we must have, $$1=(\frac{n(2^n-1)}{p})=(\frac{\frac{n}{t}}{p})(\frac{\frac{2^n-1}{t}}{p})(\frac{t^2}{p})=(1)(-1)(1)=(-1)$$which is a contradiction and so we are done except for $n=1$ which we deal with at the end. Case 2 (n is even): Let $n=2^r*s$ where $gcd(2,s)=1$ then, define $gcd(s,2^{2^r*s}-1)=a$ and let $$p \equiv 1 \ (mod \ 4), \ p \equiv 1 (mod \ \frac{r}{a}), \ p \equiv j \ (mod \ \frac{2^{2^r*s}-1}{a})$$such that $j$ is quadratic non residue of the last moduli again by Lemma 1. Notice that since $gcd(\frac{r}{a},\frac{2^{2^rs}-1}{a})=1$ and then, $gcd(\frac{r2^{2^rs}-r}{a^2},4)=1$ so a solution must exist by C.R.T. Now, consider that $$n(2^n-1)=k^2 \implies 2^rs(2^{2^rs}-1)=k^2 \implies s(2^{2^rs}-1)=m^2$$The last part holds since $gcd(2^r,r(2^rs-1))=1$ so the power of $2$ is a perfect square in itself (again a basic lemma). Therefore we must have that $s(2^{2^rs}-1)$ is a quadratic residue modulo any prime $p$. However due to our construction, by reciprocity again we must have $(\frac{\frac{r}{a}}{p})=(\frac{p}{\frac{r}{a}})=1$ and on the other hand, $(\frac{\frac{2^{2^rs}-1}{a}}{p})=(\frac{p}{\frac{2^{2^rs}-1}{a}})=(-1)$ by construction which is obvious. Finally, $gcd(n,p)=gcd(2^n-1,p)=1$ is still satisfied. We also have that $(\frac{a^2}{p})=1$ since $gcd(p,a)=gcd(p,a^2)=1$. Due to coprime moduli, through dirichlet this is an infinite A.P with primes so pick such a prime and notice that, $$1=(\frac{r(2^n-1)}{p})=(\frac{\frac{r}{a}}{p})(\frac{\frac{2^{2^rs}-1}{a}}{p})(\frac{a^2}{p})=(1)(-1)(1)=-1$$which is a contradiction! Therefore we are done with the majority cases. Finally we take care of $n=1$ which is a solution since $n(2^n-1)=1(1)=1$ and then $n=2$ which is not a solution since $2(2^2-1)=6$ isn't a perfect square. Therefore it is both necessary and sufficient. Our only solution is $\boxed{n=1}$. Q.E.D $\blacksquare$

In case of n even you can Just use the valuation 3 adik

An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction

For n even just note that $v_3(2^n - 1) = 1 + v_3(n/2) = 1 + v_3(n)$, so $v_3$ is odd. For $n$ odd i had the same way as above

Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Brilliant sol

Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why $2^p-1$ is a perfect square?

Ferreirinha wrote: Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why $2^p-1$ is a perfect square? Just use the valuation with lte

Ferreirinha wrote: Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why $2^p-1$ is a perfect square? Take q divide 2^p-1 we have the valuation q of n(2^n-1) is the same as 2^p-1

jungle_wang wrote: Find all positive integers $n$ such that $$n(2^n-1)$$is a perfect square We can easily prove by zsigmondy’s theorem that $2^n -1$ is not a perfect square for $n>2$. For $n \leq 2:n=0,n=1$ are the only solutions.Now,for $n>2$,we have that $ 2^n -1 | n$ We prove by induction that this is not true for $n>2$,showing that,for every $n \geq 3$: $$2^n-1 \geq n$$Suppose that: $$ 2^k-1 > k$$,and show that: $$2^{k+1}-1 > k+1$$. Multiplying the first inequality by 2,we get: $$2^{k+1}-2 > 2k \iff (2^{k+1} -1) > 2k+1 > k $$,so,for every $n>2, 2^n-1$ does not divide $n$ In conclusion,the only solutions are: $n=0 $ or $n=1$

Drago119 wrote: jungle_wang wrote: Find all positive integers $n$ such that $$n(2^n-1)$$is a perfect square We can easily prove by zsigmondy’s theorem that $2^n -1$ is not a perfect square for $n>2$. For $n \leq 2:n=0,n=1$ are the only solutions.Now,for $n>2$,we have that $ 2^n -1 | n$ We prove by induction that this is not true for $n>2$,showing that,for every $n \geq 3$: $$2^n-1 \geq n$$Suppose that: $$ 2^k-1 > k$$,and show that: $$2^{k+1}-1 > k+1$$. Multiplying the first inequality by 2,we get: $$2^{k+1}-2 > 2k \iff (2^{k+1} -1) > 2k+1 > k $$,so,for every $n>2, 2^n-1$ does not divide $n$ In conclusion,the only solutions are: $n=0 $ or $n=1$ We don't have that 2^n-1|n

It does'nt mean that 2^n-1 is a square free

Hamzaachak wrote: It does'nt mean that 2^n-1 is a square free Yup,my bad

mathematical717 wrote: Again, we devour this with Quadratic Reciprocity and Residues (I will provide a basic outline here.) Lemma 1 : There are quadratic non residues for any moduli $m$ except when $m=1$ or $m=2$. Basically this confirms the existence of some $a$ such that $gcd(a,m)=1$ and $\not\exists \ x : x^2 \equiv a \ (mod \ m)$. It is well known that when $p \ge 3$ there are $\frac{p-1}{2}$ non residues. So by C.R.T we can create quadratic non residues modulo $m$. This can be more rigorously and formally proven through basic group theory. Note that if $n(2^n-1)=k^2$ for some $k$. Then, $n(2^n-1)$ is a quadratic residue modulo any prime $p$. We construct a $p$ so that this fails. Case 1 (n is odd): We define $t \coloneq gcd(n,2^n-1)$ and consider the solution to $p \equiv 1 \ (mod \ 4)$, $p \equiv 1 \ (mod \ \frac{n}{t})$ and $p \equiv j \ (mod \ \frac{2^n-1}{t})$ such that $j$ is quadratic non residue of $\frac{2^n-1}{t}$ exists by Lemma 1. Notice that since $gcd(\frac{n}{t},\frac{2^n-1}{t})=1$ there exists a solution by C.R.T and then finally, $gcd(4,\frac{n(2^n-1)}{t^2})=1$ so there is an A.P satisfying the following conditions such that it is prime (by dirichlet). Also $gcd(p,n)=gcd(2^n-1,p)=1$ obviously due to the construction. Secondly dirichlet follows since all the congruences are in coprime moduli, so the resulting moduli will also be coprime (trivial lemma). Now introduce jacobi symbol and due to quadratic reciprocity and construction, $1=(\frac{p}{\frac{n}{t}})=(\frac{\frac{n}{t}}{p})$ and $(-1)=(\frac{p}{\frac{2^n-1}{t}})=(\frac{\frac{2^n-1}{t}}{p})$. The last fact follows by construction. Notice also that, $gcd(t,p)=gcd(t^2,p)=1$ and therefore, $(\frac{t^2}{p})=1$. Due to complete multiplicativity we must have, $$1=(\frac{n(2^n-1)}{p})=(\frac{\frac{n}{t}}{p})(\frac{\frac{2^n-1}{t}}{p})(\frac{t^2}{p})=(1)(-1)(1)=(-1)$$which is a contradiction and so we are done except for $n=1$ which we deal with at the end. Case 2 (n is even): Let $n=2^r*s$ where $gcd(2,s)=1$ then, define $gcd(s,2^{2^r*s}-1)=a$ and let $$p \equiv 1 \ (mod \ 4), \ p \equiv 1 (mod \ \frac{r}{a}), \ p \equiv j \ (mod \ \frac{2^{2^r*s}-1}{a})$$such that $j$ is quadratic non residue of the last moduli again by Lemma 1. Notice that since $gcd(\frac{r}{a},\frac{2^{2^rs}-1}{a})=1$ and then, $gcd(\frac{r2^{2^rs}-r}{a^2},4)=1$ so a solution must exist by C.R.T. Now, consider that $$n(2^n-1)=k^2 \implies 2^rs(2^{2^rs}-1)=k^2 \implies s(2^{2^rs}-1)=m^2$$The last part holds since $gcd(2^r,r(2^rs-1))=1$ so the power of $2$ is a perfect square in itself (again a basic lemma). Therefore we must have that $s(2^{2^rs}-1)$ is a quadratic residue modulo any prime $p$. However due to our construction, by reciprocity again we must have $(\frac{\frac{r}{a}}{p})=(\frac{p}{\frac{r}{a}})=1$ and on the other hand, $(\frac{\frac{2^{2^rs}-1}{a}}{p})=(\frac{p}{\frac{2^{2^rs}-1}{a}})=(-1)$ by construction which is obvious. Finally, $gcd(n,p)=gcd(2^n-1,p)=1$ is still satisfied. We also have that $(\frac{a^2}{p})=1$ since $gcd(p,a)=gcd(p,a^2)=1$. Due to coprime moduli, through dirichlet this is an infinite A.P with primes so pick such a prime and notice that, $$1=(\frac{r(2^n-1)}{p})=(\frac{\frac{r}{a}}{p})(\frac{\frac{2^{2^rs}-1}{a}}{p})(\frac{a^2}{p})=(1)(-1)(1)=-1$$which is a contradiction! Therefore we are done with the majority cases. Finally we take care of $n=1$ which is a solution since $n(2^n-1)=1(1)=1$ and then $n=2$ which is not a solution since $2(2^2-1)=6$ isn't a perfect square. Therefore it is both necessary and sufficient. Our only solution is $\boxed{n=1}$. Q.E.D $\blacksquare$ This was definitely brilliant, any motivation since the problem gives more the spirit of an LTE problem?

Ferreirinha wrote: Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why $2^p-1$ is a perfect square? Evaluate $v_{q}$ where $q$ is a prime divisor of $2^{p}-1$

alba_tross1867 wrote: mathematical717 wrote: Again, we devour this with Quadratic Reciprocity and Residues (I will provide a basic outline here.) Lemma 1 : There are quadratic non residues for any moduli $m$ except when $m=1$ or $m=2$. Basically this confirms the existence of some $a$ such that $gcd(a,m)=1$ and $\not\exists \ x : x^2 \equiv a \ (mod \ m)$. It is well known that when $p \ge 3$ there are $\frac{p-1}{2}$ non residues. So by C.R.T we can create quadratic non residues modulo $m$. This can be more rigorously and formally proven through basic group theory. Note that if $n(2^n-1)=k^2$ for some $k$. Then, $n(2^n-1)$ is a quadratic residue modulo any prime $p$. We construct a $p$ so that this fails. Case 1 (n is odd): We define $t \coloneq gcd(n,2^n-1)$ and consider the solution to $p \equiv 1 \ (mod \ 4)$, $p \equiv 1 \ (mod \ \frac{n}{t})$ and $p \equiv j \ (mod \ \frac{2^n-1}{t})$ such that $j$ is quadratic non residue of $\frac{2^n-1}{t}$ exists by Lemma 1. Notice that since $gcd(\frac{n}{t},\frac{2^n-1}{t})=1$ there exists a solution by C.R.T and then finally, $gcd(4,\frac{n(2^n-1)}{t^2})=1$ so there is an A.P satisfying the following conditions such that it is prime (by dirichlet). Also $gcd(p,n)=gcd(2^n-1,p)=1$ obviously due to the construction. Secondly dirichlet follows since all the congruences are in coprime moduli, so the resulting moduli will also be coprime (trivial lemma). Now introduce jacobi symbol and due to quadratic reciprocity and construction, $1=(\frac{p}{\frac{n}{t}})=(\frac{\frac{n}{t}}{p})$ and $(-1)=(\frac{p}{\frac{2^n-1}{t}})=(\frac{\frac{2^n-1}{t}}{p})$. The last fact follows by construction. Notice also that, $gcd(t,p)=gcd(t^2,p)=1$ and therefore, $(\frac{t^2}{p})=1$. Due to complete multiplicativity we must have, $$1=(\frac{n(2^n-1)}{p})=(\frac{\frac{n}{t}}{p})(\frac{\frac{2^n-1}{t}}{p})(\frac{t^2}{p})=(1)(-1)(1)=(-1)$$which is a contradiction and so we are done except for $n=1$ which we deal with at the end. Case 2 (n is even): Let $n=2^r*s$ where $gcd(2,s)=1$ then, define $gcd(s,2^{2^r*s}-1)=a$ and let $$p \equiv 1 \ (mod \ 4), \ p \equiv 1 (mod \ \frac{r}{a}), \ p \equiv j \ (mod \ \frac{2^{2^r*s}-1}{a})$$such that $j$ is quadratic non residue of the last moduli again by Lemma 1. Notice that since $gcd(\frac{r}{a},\frac{2^{2^rs}-1}{a})=1$ and then, $gcd(\frac{r2^{2^rs}-r}{a^2},4)=1$ so a solution must exist by C.R.T. Now, consider that $$n(2^n-1)=k^2 \implies 2^rs(2^{2^rs}-1)=k^2 \implies s(2^{2^rs}-1)=m^2$$The last part holds since $gcd(2^r,r(2^rs-1))=1$ so the power of $2$ is a perfect square in itself (again a basic lemma). Therefore we must have that $s(2^{2^rs}-1)$ is a quadratic residue modulo any prime $p$. However due to our construction, by reciprocity again we must have $(\frac{\frac{r}{a}}{p})=(\frac{p}{\frac{r}{a}})=1$ and on the other hand, $(\frac{\frac{2^{2^rs}-1}{a}}{p})=(\frac{p}{\frac{2^{2^rs}-1}{a}})=(-1)$ by construction which is obvious. Finally, $gcd(n,p)=gcd(2^n-1,p)=1$ is still satisfied. We also have that $(\frac{a^2}{p})=1$ since $gcd(p,a)=gcd(p,a^2)=1$. Due to coprime moduli, through dirichlet this is an infinite A.P with primes so pick such a prime and notice that, $$1=(\frac{r(2^n-1)}{p})=(\frac{\frac{r}{a}}{p})(\frac{\frac{2^{2^rs}-1}{a}}{p})(\frac{a^2}{p})=(1)(-1)(1)=-1$$which is a contradiction! Therefore we are done with the majority cases. Finally we take care of $n=1$ which is a solution since $n(2^n-1)=1(1)=1$ and then $n=2$ which is not a solution since $2(2^2-1)=6$ isn't a perfect square. Therefore it is both necessary and sufficient. Our only solution is $\boxed{n=1}$. Q.E.D $\blacksquare$ This was definitely brilliant, any motivation since the problem gives more the spirit of an LTE problem? Oh thanks a lot! The basic motivaton for me is that one of the approaches I've developed after continuous practice is to try and convert equalities to modular arithmetic and see if it fails somewhere. And since quadratic residues have been studied well by mathematicians, I said why not try.

Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction What happens in case $q<p$? How we can conclude that $2^p-1$ is a square here?

pavel kozlov wrote: Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction What happens in case $q<p$? How we can conclude that $2^p-1$ is a square here? We have q>p since the ordre is p

Hamzaachak wrote: We have q>p since the ordre is p Great, thanks for clarification! Anyway, it is better for community to write more detailed solution. I suppose that we can finish here with the fact that $v_q(2^p-1)=v_q(2^n-1)-v_q(n/p)=v_q(2^n-1)$ and it should be even.

Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why do we have all prime divisor of 2^p-1 are bigger than p ?

Manivs wrote: Hamzaachak wrote: An other solution: Let p the largest prime divisor of n We have 2^p-1 divide 2^n-1 And all prime divisor of 2^p-1 are bigger than p so for all q that divide 2^p-1 It does'nt divide n 2^p-1 is a perfect square Contradiction Why do we have all prime divisor of 2^p-1 are bigger than p ? Can you please wright a "clean" proof ? It will help a lot.

Manivs wrote: Can you please wright a "clean" proof ? It will help a lot. Here are the details Assume $n>1$ Let $p$ be the largest prime factor of $n$. Let $q$ be a prime such that $q|2^p-1$ then $ord_q(2)|p \implies ord_q(2) \in \{1,p\}$ , clearly $ord$ can't be $1$ since no prime divide $2-1=1 \implies ord_q(2)=p$. By fermat's little theorem $q|2^{q-1}-1 \implies ord_q(2)|q-1 \implies p|q-1 \implies p<q$. Thus all prime factors of $2^p-1$ are larger than prime factors of $n$.Thus $gcd(2^p-1,n)=1$. Since $p|n$ , $2^p-1|2^n-1$. Write $n=pk$ and $2^n-1=(2^p-1)r$ ,then for any prime divisor $q$ of $2^n-1$ , $v_q(2^n-1)=v_q(2^p-1)+v_q(k)$ by Lifting the exponent lemma , clearly $v_q(k)=0$ since any prime divisor of $n$ was smaller than $q$. Thus $v_q(2^n-1)=v_q(2^p-1) \implies gcd(2^p-1,r)=1$. Now $n(2^n-1)=x^2 \implies nr(2^p-1)=x^2$ where $n,r$ are coprime to $2^p-1 \implies 2^p-1=s^2$ for some natural number $s$ ,taking $\pmod 4$ both sides we obtain $3 \equiv1 \pmod 4$ .Contradiction. Thus $n=1$ is only sol.

GeoKing wrote: Manivs wrote: Can you please wright a "clean" proof ? It will help a lot. Here are the details Assume $n>1$ Let $p$ be the largest prime factor of $n$. Let $q$ be a prime such that $q|2^p-1$ then $ord_q(2)|p \implies ord_q(2) \in \{1,p\}$ , clearly $ord$ can't be $1$ since no prime divide $2-1=1 \implies ord_q(2)=p$. By fermat's little theorem $q|2^{q-1}-1 \implies ord_q(2)|q-1 \implies p|q-1 \implies p<q$. Thus all prime factors of $2^p-1$ are larger than prime factors of $n$.Thus $gcd(2^p-1,n)=1$. Since $p|n$ , $2^p-1|2^n-1$. Write $n=pk$ and $2^n-1=(2^p-1)r$ ,then for any prime divisor $q$ of $2^n-1$ , $v_q(2^n-1)=v_q(2^p-1)+v_q(k)$ by Lifting the exponent lemma , clearly $v_q(k)=0$ since any prime divisor of $n$ was smaller than $q$. Thus $v_q(2^n-1)=v_q(2^p-1) \implies gcd(2^p-1,r)=1$. Now $n(2^n-1)=x^2 \implies nr(2^p-1)=x^2$ where $n,r$ are coprime to $2^p-1 \implies 2^p-1=s^2$ for some natural number $s$ ,taking $\pmod 4$ both sides we obtain $3 \equiv1 \pmod 4$ .Contradiction. Thus $n=1$ is only sol. Thank you very much ! It has helped me a lot !