Impossible divisibility

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

11 users

TOPICS

No tags match your search

M

No tags match your search

M

Impossible divisibility

G H J

Reveal topic tags

modular arithmetic

Quadratic Residues

quadratic reciprocity

L

G H BBookmark kLocked kLocked NReply

Source: Romanian TST 3 2008, Problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1145 posts

#1 h Jun 7, 2008, 5:21 PM • 6 Y

Y by nguyendangkhoa17112003, Adventure10, megarnie, Mango247, and 2 other users

Let $m,\ n \geq 3$ be positive odd integers. Prove that $2^{m}-1$ doesn't divide $3^{n}-1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#2 h Jun 7, 2008, 5:29 PM • 2 Y

Y by Adventure10, Mango247

$3^n-1\not |2^m-1$ , because $3^n-1$ even, $2^m-1$ odd.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

337 posts

#3 h Jun 7, 2008, 9:38 PM • 18 Y

Y by fish135, gethd, kgo, nguyendangkhoa17112003, Supercali, Williamgolly, The_Giver, karitoshi, Wizard0001, pavel kozlov, Kanep, nguyenvuthanhha, Adventure10, Mango247, and 4 other users

@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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1363 posts

Erken

#4 h Jun 8, 2008, 8:16 AM • 1 Y

Y by Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#5 h Jun 9, 2008, 2:32 PM • 3 Y

Y by Adventure10, Mango247, Want-to-study-in-NTU-MATH

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9 posts

#6 h Jun 29, 2008, 10:59 AM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

337 posts

#7 h Jun 30, 2008, 10:05 AM • 2 Y

Y by Adventure10, Mango247

$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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AndreiAndronache

88 posts

AndreiAndronache

#8 h Aug 25, 2012, 3:25 PM • 2 Y

Y by pavel kozlov, Adventure10

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#10 h Sep 22, 2015, 6:02 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#12 h Feb 15, 2019, 5:45 AM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

544 posts

#13 h Mar 27, 2019, 3:38 PM • 2 Y

Y by Adventure10, Mango247

QR

This post has been edited 1 time. Last edited by shankarmath, Mar 27, 2019, 3:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#14 h Sep 6, 2019, 9:34 PM • 6 Y

Y by pad, AlastorMoody, skrublord420, Kobayashi, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#15 h May 31, 2020, 1:20 AM • 1 Y

Y by Want-to-study-in-NTU-MATH

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#16 h Jun 3, 2020, 12:15 AM • 3 Y

Y by Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

algebra_star1234

2467 posts

algebra_star1234

#17 h Jun 13, 2020, 11:40 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#18 h Jun 14, 2020, 4:38 AM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Quantum_fluctuations

1282 posts

Quantum_fluctuations

#19 h Aug 1, 2020, 10:19 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

626 posts

#20 h Dec 31, 2020, 1:43 AM • 2 Y

Y by pavel kozlov, Mathandski

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#21 h Dec 31, 2020, 6:42 PM • 1 Y

Y by Mathandski

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$

This post has been edited 2 times. Last edited by jj_ca888, Dec 31, 2020, 6:43 PM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#22 h Mar 1, 2021, 10:33 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

277 posts

#23 h Aug 21, 2021, 10:07 PM

Y by

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$

This post has been edited 1 time. Last edited by bora_olmez, Aug 21, 2021, 10:07 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1492 posts

#24 h Oct 2, 2021, 3:10 AM

Y by

$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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trying_to_solve_br

191 posts

trying_to_solve_br

#25 h Oct 4, 2021, 3:29 PM

Y by

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)$

This post has been edited 1 time. Last edited by trying_to_solve_br, Oct 4, 2021, 3:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nguyenvuthanhha

482 posts

nguyenvuthanhha

#27 h Oct 19, 2021, 8:39 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#28 h Nov 1, 2021, 3:31 AM

Y by

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.

This post has been edited 2 times. Last edited by AwesomeYRY, Nov 1, 2021, 3:40 AM
Reason: aops duplicate

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5003 posts

#30 h Jan 5, 2022, 3:36 PM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8868 posts

#31 h Apr 23, 2023, 2:46 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

480 posts

#32 h Aug 11, 2023, 11:51 AM • 1 Y

Y by HoripodoKrishno

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. :stretcher:

:stretcher:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#33 h Apr 5, 2024, 7:26 PM • 1 Y

Y by Mathandski

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1748 posts

OronSH

#34 h Apr 28, 2024, 4:28 PM • 1 Y

Y by Mathandski

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

150 posts

Markas

#35 h Jul 13, 2024, 2:57 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

195 posts

onyqz

#36 h Aug 9, 2024, 10:26 AM • 1 Y

Y by Mathandski

posting for storage
Click to reveal hidden text

This post has been edited 1 time. Last edited by onyqz, Aug 27, 2024, 4:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

629 posts

maxal

#37 h Aug 21, 2024, 10:33 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

773 posts

#38 h Oct 15, 2024, 8:03 PM

Y by

$\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

66 posts

zuat.e

#39 h Jan 26, 2025, 5:16 PM

Y by

Assume otherwise, that is $2^a-1\mid3^b -1$ with $b$ even and $a>1$ , hence $3^b\equiv1\pmod{2^a-1}$ , therefore $3^{b+1}\equiv3\pmod{2^a-1}$ , so $3$ is a quadratic residue $\pmod{2^a-1}$ , consequently: $\prod_{i=1}^k(\frac{3}{p_i})=(\frac{3}{2^a-1})\equiv-(\frac{2^a-1}{3})\equiv-(\frac{1}{3})\equiv-1$ , hence $3$ isn't a $QR$ for some $p_i\mid k$ , hence $3$ isn't a $QR$ $\pmod{2^a-1}$

This post has been edited 1 time. Last edited by zuat.e, Jan 26, 2025, 5:23 PM
Reason: My solution was wrong

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

640 posts

cursed_tangent1434

#40 h Apr 29, 2025, 6:03 AM

Y by

We consider $a>1$ and $b$ odd in what follows. Clearly $a$ must be odd since if $a$ is even, $3 \mid 2^a-1 \mid 3^b-1$ which is a clear contradiction for all positive integers $b$ . Note that for each prime $p \mid 2^a-1$ ,
$\begin{align*} 3^b & \equiv 1 \pmod{p}\\ 3 & \equiv \left (\frac{1}{3^{{\frac{b-1}{2}}}}\right)^2 \pmod{p} \end{align*}$ which implies that $3$ is a quadratic residue $\pmod{p}$ for each prime divisor $p$ of $2^a-1$ . Further, the Law of Quadratic Reciprocity states that
$\left(\frac{p}{3}\right)=\left(\frac{3}{p}\right)\left(\frac{p}{3}\right) = (-1)^{\frac{p-1}{2}}$ since $3$ is a quadratic residue $\pmod{p}$ . Now if $p \equiv 1 \pmod{4}$ this implies $p$ is a quadratic residue $\pmod{3}$ so $p \equiv 1 \pmod{3}$ . And similarly if $p \equiv 3 \pmod{4}$ this implies $p$ is a non-quadratic residue $\pmod{p}$ so $p \equiv 2 \pmod{3}$ . Hence, any prime divisor $p$ of $2^a-1$ must be $\pm 1\pmod{12}$ .

However, if $a$ is even, $2^a-1 \equiv -1 \pmod{4}$ since $a>1$ and $2^a-1 \equiv 1 \pmod{3}$ . Hence, we must have $2^a-1 \equiv 7 \pmod{12}$ . But if each prime divisor of $2^a-1$ is $\pm 1 \pmod{12}$ , $2^a-1$ must also be $\pm 1 \pmod{12}$ which is a clear contradiction. Hence it is impossible to have $a>1$ and $b$ being odd simultaneously which finishes the problem.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a