Let $ m,\ n \geq 3$ be positive odd integers. Prove that $ 2^{m}-1$ doesn't divide $ 3^{n}-1$.
Problem
Source: Romanian TST 3 2008, Problem 3
Tags: quadratics, modular arithmetic, number theory, prime factorization, number theory proposed
07.06.2008 20:29
$ 3^n-1\not |2^m-1$, because $ 3^n-1$ even, $ 2^m-1$ odd.
08.06.2008 00:38
@Rust: divides means "is a divisor of", not "is divisible by". Nice problem . Assume, to the contrary, that there are such odd numbers $ m,n\ge3$ for which $ 2^m-1|3^n-1$. Let $ p$ be a prime divisor of $ 2^m-1$ of the form $ 4k+3$. Because $ p|3^n-1$, we have that $ d=\text{ord}_3(p)$ is odd. Since $ d|p-1=4k+2$, we have $ d|2k+1$, hence $ 3^{\frac{p-1}2}=\binom{\underline3}p=1$. Then, by the Quadratic Reciprocity Law, we have $ \binom{\underline3}p\cdot\binom{\underline p}3=(-1)^{\frac{3-1}2\cdot\frac{p-1}2}=-1$ hence $ \binom{\underline p}3=-1$, so $ p=3t+2$. Let now $ p$ be a prime divisor of $ 2^m-1$ of the form $ 4k+1$. A reasoning just as above and $ \binom{\underline3}p\cdot\binom{\underline p}3=(-1)^{\frac{3-1}2\cdot\frac{p-1}2}=1$ leads to $ \binom{\underline p}3=1$, hence $ p=3t+1$. So let $ M$ be the multiset of prime divisors $ p$ of $ 2^m-1$ of the form $ 4k+3$, containing each prime with multiplicity equal to its exponent in the prime factorization of $ 2^m-1$. Because $ 2^m-1\equiv 3\pmod 4$, $ |M|$ is odd. But $ M$ contains precisely all prime divisors $ p$ of the form $ 3t+2$ of $ 2^m-1$. Then considering $ \text{mod}$ $ 3$, we have $ 2^m-1\equiv 2^{|M|}=2\pmod 3$, Contradiction.
08.06.2008 11:16
Suppose that $ 2^{m} - 1$ divides $ 3^{n} - 1$.As we know $ n$ is odd,let $ n = 2k - 1$,where $ k\geq 2$. It is easy to understand that $ 2^{m} - 1\equiv - 5$ mod $ 12$. Since $ 2^{m} - 1$ is not divisible by $ 3$,we conclude that all prime divisors of $ 2^{m} - 1$ are congruent to either $ + 5, - 5$,or $ + 1, - 1$ mod $ 12$,but as we know $ 2^{m} - 1\equiv - 5$, it follows that, there exist $ p\equiv 5$ or $ p\equiv - 5$ mod $ 12$ and $ p$ divides $ 2^{m} - 1$,thus it divides $ 3^{n} - 1$,too,but then $ p$ divides $ 3(3^{n} - 1)$ as well,hence $ 3^{2k} = 3^{n + 1}\equiv 3$ mod $ p$,so $ 3$ is a quadratic residue mod $ p$,but this contradicts to the quadratic reciprocity theorem,because $ p\equiv 5$ or $ - 5$ mod $ 12$.
09.06.2008 17:32
Other solution (same free mind but have a bit difference) Call p is a odd prime divisor of $ 3^n - 1$ $ \Rightarrow p|3^{\frac {n + 1}{2}} - 3$ $ \Rightarrow \frac (\frac {3}{p}) = 1$ $ \Rightarrow p\equiv 1 (\mod 12)$ or $ p\equiv - 1 (\mod 12)$ So if $ k|3^n - 1$ then $ k\equiv 1 (\mod 12)$ or $ k\equiv - 1(\mod 12)$ But $ 2^n - 1\equiv 7 (\mod 12)$ ,it give contradiction . More than $ rad(2^m - 1) \not |3^m - 1$
29.06.2008 13:59
freemind wrote: Let $ p$ be a prime divisor of $ 2^m - 1$ of the form $ 4k + 3$. Because $ p|3^n - 1$, we have that $ d = \text{ord}_3(p)$ is odd. Since $ d|p - 1 = 4k + 2$, we have $ d|2k + 1$, hence $ 3^{\frac {p - 1}2} = \binom{\underline3}p = 1$. how you can say that if dl 4k+2 then dl 2k+1 for example p=7 7l 3^6-1 but 7l 3^3-1
30.06.2008 13:05
$ d$ is odd because $ d|n$ and $ n$ is odd. kim_ina_88 wrote: freemind wrote: Let $ p$ be a prime divisor of $ 2^m - 1$ of the form $ 4k + 3$. Because $ p|3^n - 1$, we have that $ d = \text{ord}_3(p)$ is odd. Since $ d|p - 1 = 4k + 2$, we have $ d|2k + 1$, hence $ 3^{\frac {p - 1}2} = \binom{\underline3}p = 1$. how you can say that if dl 4k+2 then dl 2k+1 for example p=7 7l 3^6-1 but 7l 3^3-1
25.08.2012 18:25
Very simple, if we use Jacobi's symbol: We note $3^{\dfrac{n-1}{2}}=a\Rightarrow 3a^2\equiv 1(mod\,\; 2^m-1)\Rightarrow (3a)^2\equiv 3(mod\,\; 2^m-1)\Rightarrow (\dfrac{3}{2^m-1})=1$. By use quadratic reciprocity, $(\dfrac{2^m-1}{3})*(-1)^{\dfrac{3-1}{2}*\dfrac{2^m-1-1}{2}}=1\Rightarrow (\dfrac{2^m-1}{3})=-1$, obviously false, because $2^m\equiv 2(mod\,\; 3)$.
22.09.2015 09:02
After noticing that there exists a prime $p$ such that $p \mid 2^m-1$ and that $p \equiv 5,7 (mod 12)$ we conclude by quadratic reciprocity law.
15.02.2019 08:45
I will solve the following alternative formulation of this problem: Alternative Formulation wrote: Let $a$ and $b$ be positive integers such that $2^a - 1$ divides $3^b - 1$. Prove that either $a = 1$ or $b$ is even. Solution: Suppose $a > 1$ and $b$ is odd. Let $p \mid 2^a - 1$ be a prime. Then, \begin{align*} p &\mid 3^b - 1 \\ p &\mid 3^{b + 1} - 3. \end{align*}Hence $\left(\frac{3}{p}\right) = 1$. If $p \equiv 1 \pmod{4}$, we have by Quadratic Reciprocity that \begin{align*} \left(\frac{p}{3}\right) &= \left(\frac{3}{p}\right) \\ &= 1, \end{align*}so $p \equiv 1 \pmod{12}$. If $p \equiv -1 \pmod{4}$, we have by Quadratic Reciprocity that \begin{align*} \left(\frac{p}{3}\right) &= -\left(\frac{3}{p}\right) \\ &= -1, \end{align*}so $p \equiv -1 \pmod{12}$. Hence, $p$ must be of the form $12k \pm 1$. Since $a > 1$, we have \begin{align*} 2^a - 1 &\equiv -1 \pmod{4}. \end{align*}Also, note that \begin{align*} 2^a - 1 \equiv 0, 1 \pmod{3}. \end{align*}Hence \begin{align*} 2^a - 1 \equiv 3, 7 \pmod{12}. \end{align*}Hence there exists a prime $q \mid 2^a - 1$ that is not of the form $12k \pm 1$, contradiction. Thus, either $a = 1$ or $b$ is even, as desired. $\Box$
27.03.2019 18:38
07.09.2019 00:34
Suppose $p$ is some prime factor of $3^n-1$. Then, we have that \[\left(3^{\frac{n+1}{2}}\right)^2\equiv 3\pmod{p},\]so $3$ is a quadratic residue mod $p$. Using quadratic reciprocity, this tells us that $p\equiv\pm 1\pmod{12}$. Therefore, all the prime factors of $2^m-1$ are $\pm 1\pmod{12}$, so $2^m-1\equiv\pm 1\pmod{12}$, so in particular, $2^m\equiv 2\pmod{4}$. Thus, $m=1$, which is a contradiction since $m\ge 3$, so we're done.
31.05.2020 04:20
Suppose $b$ is odd and $2^a-1\mid 3^b-1$ for some $a.$ Consider some prime $p$ dividing $2^a-1.$ We have $$3^b-1\equiv 0\pmod{p}$$$$\implies 3^{b+1}\equiv 3\pmod{p}$$$$\implies \left(\frac{3}{p}\right)=1.$$If $p\equiv 1\pmod{4},$ then $$p\equiv \left(\frac{p}{3}\right)\stackrel{QR}{=}\left(\frac{3}{p}\right)=1\pmod{3}.$$If $p\equiv 3\pmod{4},$ then $$p\equiv \left(\frac{p}{3}\right)\stackrel{QR}{=}-\left(\frac{3}{p}\right)=-1\pmod{3}.$$Therefore, $p\equiv\pm 1\pmod{12}.$ Since our choice of $p$ was arbitrary, we must have $$2^a-1\equiv\pm 1\pmod{12}.$$This is true if and only if $a=1,$ so we are done.
03.06.2020 03:15
We do the following stronger problem. Stronger Statement wrote: Let $a$ and $b$ be positive integers such that $2^a-1\mid 3^b-1$. Prove that either $a=1$ or $b$ is even. Suppose otherwise. As $2^a-1 > 1$, $2^a-1=N$ has some prime divisors $p$. Claim: For $p\mid N$, we have that $p\equiv \pm 1\pmod{12}$. Solution: Let $o_p(3)$ be the order of $b$ modulo $p$. As $p\mid N\mid 3^b-1$, we have $o_p(3)\mid b$. Since $b$ is odd, we must have $o_p(3)\mid \frac{p-1}{2}$, since we can disregard powers of $2$ that divide $p-1$. This implies that $3$ is a quadratic residue modulo $p$, so $p\equiv \pm 1\pmod{12}$ as desired. $\fbox{}$ Now, note that this implies $N\equiv \pm 1\pmod{12}$. As $N\equiv -1\pmod{4}$, we get that $N\equiv -1\pmod{12}$. In particular, $2^a-1=N\equiv -1\pmod{3}$. But this would imply $3\mid 2^a$, absurd.
14.06.2020 02:40
Since $b$ is odd, we have $3^{b+1} \equiv 3 \pmod{2^{a}-1}$ is a quadratic residue. By quadratic reciprocity, \[ \left( \frac{3}{2^{a}-1}\right)=\left(\frac{2^{a}-1}{3}\right) (-1)^{2^{a-1}-1} = 1 \cdot -1 = -1 .\]for $a > 1$. Therefore $b$ cannot be odd.
14.06.2020 07:38
algebra_star1234 wrote: Since $b$ is odd, we have $3^{b+1} \equiv 3 \pmod{2^{a}-1}$ is a quadratic residue. By quadratic reciprocity, \[ \left( \frac{3}{2^{a}-1}\right)=\left(\frac{2^{a}-1}{3}\right) (-1)^{2^{a-1}-1} = 1 \cdot -1 = -1 .\]for $a > 1$. Therefore $b$ cannot be odd. This is close, but it doesn't work because it's missing the $(-1)^\frac{3-1}{2}=-1$ term, so \[ \left(\frac{3}{2^a-1}\right) = 1 \] It would work if $3$ was changed in the original problem to a value that is 1 mod 4, such as $5$.
01.08.2020 13:19
Rust wrote: $ 3^n-1\not |2^m-1$, because $ 3^n-1$ even, $ 2^m-1$ odd. Odd number can divide an even number but even number can never divide an odd number.
31.12.2020 04:43
We have that $3^{b+1} \equiv 3 \pmod{2^a-1}$ is a quadratic residue; by quadratic reciprocity we have $$\left( \frac{3}{2^a-1} \right) \left( \frac{2^a-1}{3} \right) = (-1)^{(2^a-2)(2)/4} = -1$$so $2^a-1$ is a quadratic nonresidue $\pmod{3}$. This is impossible.
31.12.2020 21:42
The case where $a = 1$ is trivial. Otherwise, FTSoC assume $a > 1$ and $b$ is odd. Also ote that $a$ must also be odd, else $3 \mid 2^a - 1$. Select a prime $p$ dividing $2^a - 1$; note that $2^{a+1} \equiv 2 \pmod p$ and $3^{b+1} \equiv 3 \pmod p$. Hence,\[\left(\frac{2}{p}\right) = \left(\frac{3}{p}\right) = 1\]must be true. From $\left(\tfrac{2}{p}\right) = 1$, we get that $\tfrac18(p^2 - 1)$ is even which yields $p \equiv \pm 1 \pmod 8$. If $p \equiv 1 \pmod 8$, then\[1 = \left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)\]and clearly $p \neq 3$ since $a$ is odd, so $p \equiv 1 \pmod 3$. Thus $p \equiv 1 \pmod {24}$. If $p \equiv -1 \pmod 8$, then\[1 = \left(\frac{3}{p}\right) = -\left(\frac{p}{3}\right)\]so $p \equiv -1 \pmod 3$. Thus $p \equiv -1 \pmod {24}$. Since all primes dividing $2^a - 1$ are $\pm 1$ modulo $24$, the number $2^a - 1$ itself must be $\pm 1$ mod $24$. This reduces to either $24 \mid 2^a$ or $24 \mid 2^{a} - 2$ which are both impossible, so we have our desired contradiction. $\blacksquare$
02.03.2021 01:33
Suppose $2^m-1\mid 3^n-1$. Suppose $p\mid 2^m-1$, so $p\mid 3^n-1$. Hence \[ \left(3^{\frac{n+1}{2}}\right)^2 \equiv 3^{n+1} \equiv 3 \pmod{p} \implies \left(\frac{3}{p}\right)=1. \]Hence $p\equiv \pm1 \pmod{12}$. Hence all prime factors of $2^m-1$ are $\pm 1 \pmod{12}$, so $2^m-1 \equiv \pm 1\pmod{12}$. So $2^m\equiv 2 \pmod{12}$, which is a contradiction by mod 4.
22.08.2021 01:07
Cool. We will use the generalization of the Law of Quadratic Reciprocity for the Jacobi Symbol. Assume FTSOC that $2^m-1 \mid 3^{2k+1}-1$, then notice that $3$ is a quadratic residue $\pmod{2^m-1}$. Moreover that $m$ must be odd as otherwise $3 \mid 2^m-1$ which is not possible and consequently, $$2^m-1 \equiv 1 \pmod{3}$$We have that , $$1 = \left(\frac{2^m-1}{3}\right)= \left(\frac{3}{2^m-1}\right) \cdot \left(\frac{2^m-1}{3}\right) = (-1)^{\frac{2(m-1)}{4}} = -1$$as $m$ is odd which is a contradiction. $\blacksquare$
02.10.2021 06:10
$a=1$ is trivial so assume $a>1.$ Consider some $p \mid 2^{a}-1.$ Then, $2^{a+1} \equiv 2 \pmod{p},$ meaning \[ \left( \frac{2}{p} \right) = (-1)^{1/8 (p^2-1)} =1 \iff p \equiv \pm 1 \pmod{8} \]as $a+1$ is even, meaning $2$ is a QR mod $p.$ Similarly, $p \mid 3^{b}-1$ and furthermore \[ \left( \frac{3}{p} \right) \left( \frac{p}{3} \right) = (-1)^{1/2(p-1)}. \]If $p \equiv 2 \pmod{3},$ then $ \left( \frac{p}{3} \right) = -1,$ which also gives $p \equiv -1 \pmod{3}.$ Combined, these give $p \equiv -1 \pmod{24}.$ The other case gives $p \equiv 1 \pmod{24},$ so $p \equiv \pm 1 \pmod{24}.$ Therefore, if $p \mid 2^{a}-1$ we also have $p \equiv \pm 1 \pmod{24}.$ Combined this implies that $2^{a} -1 \equiv \pm 1 \pmod{24}$ which are both contradictions due to divisibility reasons. Thus there are no solutions.
04.10.2021 18:29
Can someone check this sol? Obviously there exists a prime $p$ congruent to 3 mod 4 dividing $2^m-1$. Now, notice that as $m,n$ are odd, $m=2x+1$ and $n=2y+1$ thus $2^m\equiv 1 (p) \implies 2^{2x}.2\equiv 1 (p) \implies (\frac{1/2}{p})=1$, thus we have by legendre symbol properties that $(\frac{2.1/4}{p})=1=(\frac{1/4}{p}).(\frac{2}{p})=1$ which implies $2$ is a quadratic residue mod $p$, similarly for $3$. Respectively, this implies that $p \equiv \{1,-1\} (8), p \equiv \{1,-1\} (12)$, but as $p\equiv 3 (4)$ this implies $p\equiv -1 (mod 8)$ and $p \equiv -1 (mod 12)$. Quadratic recyprocity gives: $(\frac{3}{p}).(\frac{p}{3})=(-1)^{p-1/2}.(-1)^{1}=1$ and thus $p\equiv 1 (3)$ or $p=3$, which both contradict the fact that $p\equiv -1 (mod 12)$
19.10.2021 11:39
yayups wrote: Suppose $p$ is some prime factor of $3^n-1$. Then, we have that \[\left(3^{\frac{n+1}{2}}\right)^2\equiv 3\pmod{p},\]so $3$ is a quadratic residue mod $p$. Using quadratic reciprocity, this tells us that $p\equiv\pm 1\pmod{12}$. Therefore, all the prime factors of $2^m-1$ are $\pm 1\pmod{12}$, so $2^m-1\equiv\pm 1\pmod{12}$, so in particular, $2^m\equiv 2\pmod{4}$. Thus, $m=1$, which is a contradiction since $m\ge 3$, so we're done. very good and correct solution
01.11.2021 06:31
If $a=1$, clearly $2^a-1=1\mid 3^b-1$. Otherwise, if $a$ is even then $3\mid 2^a-1$, so $3\mid 2^a-1\mid 3^b-1$, a contradiction. Thus, we will only consider odd $a$. Claim 1:For $q\geq 5$, 3 is a quadratic residue mod $q$ if and only if $q\equiv 1,-1\pmod{12}$. Proof:If $q\equiv 1\pmod{4}$, then $q$ must be a quadratic residue mod 3, so $q\equiv 1\pmod{3}$ too, so $q\equiv 1$. Otherwise, if $q\equiv 3\pmod{4}$, then $q\equiv 2\pmod{3}$ by quadratic recirprocity, so $q\equiv -1$.$\square$ Claim 2:For odd $a$, 3 is not a quadratic residue mod $2^a-1$ Proof: Note that $2,3 \nmid 2^a-1$, and $2^a-1 \equiv 3 \pmod{4}$ and $2^a-1\equiv 1 \pmod{3}$, so $2^a-1\equiv 7\pmod{12}$. Thus, there exists some $q\not\equiv -1,1$ such that $q\mid 2^a-1$. Since by the previous claim, $a$ is not a quadratic residue mod $q$, $a$ is not a quadratic residue mod $2^a-1$.$\square$ Thus, if $b$ is odd, then $3^b=1$ is also not a quadratic residue mod $2^a-1$ a clear contradiction.
05.01.2022 18:36
Ok how broken is quadratic reciprocity We make use of the fact that if a prime $p$ divides $a^k-1$ for $k$ odd, then $a$ is a quadratic residue $\pmod{p}$, since $\mathrm{ord}_p(a)=\tfrac{p-1}{d}$ for some $d \mid k$. Assume otherwise, and let $p$ be a prime dividing $2^m-1$. Then from the above fact we obtain $(\tfrac{2}{p})=1 \implies p \equiv 1,7 \pmod{8}$. Now, prime factorize $$2^m-1=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}.$$Since $2^m-1 \equiv 7 \pmod{8}$, there are an odd number of indices $i$ such that $e_i$ is odd and $p_i \equiv 7 \pmod{8}$—call these indices special. Note that the non-special indices $i$ either satisfy $p_i \equiv 1 \pmod{8}$ or $p_i \equiv 7 \pmod{8}$ and $e_i$ is even. Now, by assumption, we must have $p_i \mid 3^n-1 \implies (\tfrac{3}{p_i})=1$. Consider the following cases: $p_i \equiv 1 \pmod{8}$. Then by quadratic reciprocity $$\left(\frac{3}{p_i}\right)\left(\frac{p_i}{3}\right)=1 \implies \left(\frac{p_i}{3}\right)=1 \implies p_i \equiv 1 \pmod{3}$$ $p_i \equiv 7 \pmod{8}$. Then by quadratic reciprocity $$\left(\frac{3}{p_i}\right)\left(\frac{p_i}{3}\right)=1 \implies \left(\frac{p_i}{3}\right)=-1 \implies p_i \equiv 2 \pmod{3}$$ Take both sides of $2^m-1=p_1^{e_1}\ldots p_k^{e_k}$ modulo $3$. The LHS is clearly $1 \pmod{3}$. However, since the only $i$ with $p_i^{e_i} \equiv 2 \pmod{3}$ are the special $i$, of which there are an odd number, and the rest are $1 \pmod{3}$—either because $p_i \equiv 1 \pmod{3}$ or $e_i$ is even—it follows that the RHS is $2 \pmod{3}$, which is a contradiction. Thus no such $(m,n)$ exist, as desired. $\blacksquare$
23.04.2023 05:46
Suppose that $b$ is odd. If $a$ is even, then for mod $3$ yields a contradiction. Thus assume $a$ is odd, Let $p \mid 2^a - 1$; thus $2^a \equiv 1 \pmod p$ for $a$ odd implies $\left(\frac 2p\right) = 1$. Similarly, $\left(\frac 3p\right) = 1$. On the other hand, the first equality holds for $p \equiv \pm 1 \pmod 8$, and the other equality holds for $$(-1)^{(p-1)/2}\left(\frac p3\right) = 1 \iff p \equiv \pm 1 \pmod {12}.$$So $p \equiv \pm 1 \pmod {24}$ and $2^a - 1 \equiv \pm 1 \pmod {24}$, contradiction.
11.08.2023 14:51
Here is the phrasing I received the problem in. Romania TST 2008 modified wrote: Let $a > 1$ and $b > 1$ be positive integers such that $2^a-1\mid 3^b-1$. Prove that $b$ is even. The following below is my solution. Firstly, if $a$ is even, then we get that $3 \mid 2^a-1\mid 3^b-1$ which gives a contradiction. So $a$ must be odd. Furthermore, FTSOC assume that $b$ is odd too. So we now use $a=2m+1$ and $b=2n+1$, where $m$ and $n$ are +ve integers. Now pick any prime $p$ such that $p\mid 2^{2m+1}-1$. Clearly $p\not=3$. This gives us that $2^{2m+1}\equiv 1\pmod{p}\implies 2^{2(m+1)}\equiv 2\pmod{p}$, which means that $2$ is a quadratic residue $\pmod{p}$. Similarly, we get that $p\mid 2^{2m+1}\mid 3^{2n+1}$ which further gives that $3$ is a quadratic residue too. Now we proceed using Legendre's notation. Firstly, from the fact that $\left(\dfrac{2}{p}\right)=1$, we get that $p\equiv \left\{+1,-1\right\}\pmod{8}$. Also, from $\left(\dfrac{3}{p}\right)=1$, we get that $\left(\dfrac{p}{3}\right)=(-1)^{\dfrac{3-1}{2}\cdot\dfrac{p-1}{2}}\cdot\left(\dfrac{3}{p}\right)=(-1)^{\dfrac{p-1}{2}}$. Now if $p\equiv 1\pmod{8}$, then we get that $\left(\dfrac{p}{3}\right)=-1$ which further gives us that $p\equiv 1\pmod{3}$. Similarly if $p\equiv -1\pmod{8}$, then we get that $p\equiv -1\pmod{3}$. Now finally combining these two using C.R.T., we get that $p\equiv\left\{+1,-1\right\}\pmod{24}$. Now as $2^{2m+1}-1$ is just a product of a bunch of such primes, we get that $2^{2m+1}-1\equiv \left\{+1, -1\right\}\pmod{24}$. Both of the cases give simple modular contradictions and we are done.
05.04.2024 22:26
Suppose there exist $a,b$ such that $b$ is odd and $a>1$ and $2^a-1\mid 3^b-1$. Note that $3\nmid 3^b-1$, which means $3\nmid 2^a-1$, and hence $a$ is odd. Let $p$ be an odd prime such that $p\mid 2^a-1\mid 3^b-1$. Since $a,b$ are odd, $\left(\frac 2p\right)=\left(\frac 3p\right)=1$. Claim: $p\equiv\pm1\pmod{24}$. Proof. Since $\left(\frac 2p\right)=1$, we have $p\equiv\pm1\pmod{8}$. Case 1. $p\equiv 1\pmod{8}$. Then, by Quadratic Reciprocity Law, we have $\left(\frac p3\right)=\left(\frac 3p\right)\left(\frac p3\right)=1$, which means $p\equiv 1\pmod{3}$. Hence, $p\equiv1\pmod{3}$. Combining, we get $p\equiv 1\pmod {24}$. Case 2. $p\equiv -1\pmod{8}$. Similar to above, we get $p\equiv -1\pmod{24}$. Note that this means $2^a-1\equiv\pm1\pmod{24}$, either of which is impossible. $\blacksquare$
28.04.2024 19:28
If $3^n \equiv 1\pmod{2^m-1}$ then $3$ has odd order w.r.t. all primes dividing $2^m-1,$ so it is a QR mod all primes dividing $2^m-1.$ Then quadratic reciprocity gives $\left(\frac3{2^m-1}\right)=-\left(\frac{2^m-1}3\right)=-\left(\frac13\right)=-1,$ thus there is some $p\mid 2^m-1$ for which $\left(\frac3p\right)=-1,$ contradiction
13.07.2024 17:57
Let b be odd for the sake of contradiction. Now let a be even $\Rightarrow$ $3 \mid 2^a - 1$ $\Rightarrow$ $3 \mid 3^b - 1$, which is impossible $\Rightarrow$ a is odd. We have that a and b are odd. Let $p \mid 2^a - 1$ $\Rightarrow$ $p \mid 3^b - 1$ $\Rightarrow$ $2^a \equiv 1 \pmod p$ and $3^b \equiv 1 \pmod p$ and now considering a and b are odd we get that $2^{a+1} \equiv 2 \pmod p$ and $3^{b+1} \equiv 3 \pmod p$ $\Rightarrow$ $\left(\frac 2p\right) = \left(\frac 3p\right) = 1$. Since $\left(\frac 2p\right) = (-1)^{\frac{p^2-1}{8}} = 1$ we have that $p \equiv \pm 1 \pmod 8$. Also $\left(\frac 3p \right)\left(\frac p3 \right) = (-1)^{\frac{(p-1)(3-1)}{4}} = (-1)^{\frac{p-1}{2}}$. If $p \equiv 1 \pmod 8$ we have that $\left(\frac p3 \right) = 1$ $\Rightarrow$ $p \equiv 1 \pmod 3$ $\Rightarrow$ $p \equiv 1 \pmod {24}$. If $p \equiv -1 \pmod 8$ we have that $\left(\frac p3 \right) = -1$ $\Rightarrow$ $p \equiv -1 \pmod 3$ $\Rightarrow$ $p \equiv -1 \pmod {24}$ $\Rightarrow$ in conclusion $p \equiv \pm 1 \pmod {24}$. Since each different prime divisor of $2^a - 1$ is $\equiv \pm 1 \pmod {24}$ it follows that $2^a - 1 \equiv \pm 1 \pmod {24}$. If $2^a - 1 \equiv -1 \pmod {24}$ we have that $24 \mid 2^a$, which is obviously impossible $\pmod 3$. If $2^a - 1 \equiv 1 \pmod {24}$ we have that $24 \mid 2^a - 2$ $\Rightarrow$ $8 \mid 2^a - 2$, which is impossible for $a > 3$ $\Rightarrow$ we get the desired contradiction.
09.08.2024 13:26
posting for storage
22.08.2024 01:33
My generalization published as Problem 3883 in Crux Mathematicorum 39:9 (2013): Let $a,b,c,d$ be positive integers such that $a+b$ and $ad+bc$ are odd. Prove that if $2^a - 3^b>1$, then $2^a - 3^b$ does not divide $2^c + 3^d$.