All prime factors under 8

The post below has been deleted. Click to close.

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

qwedsazxc

167 posts

qwedsazxc

#1 h Mar 26, 2023, 6:29 AM • 1 Y

Y by DEKT

Find all positive integers $n$ satisfying the following.
$2^n-1 \text{ doesn't have a prime factor larger than } 7$

This post has been edited 1 time. Last edited by qwedsazxc, Mar 26, 2023, 6:56 AM

Z K Y

The post below has been deleted. Click to close.

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

seojun8978

73 posts

seojun8978

#2 h Mar 26, 2023, 6:50 AM

Y by

I took the test and I solved this problem. It needs some long calculations but they are not that hard. The answer seems to be 1,2,3,4,6

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9045 posts

Tintarn

#3 h Mar 26, 2023, 6:54 AM • 4 Y

Y by seojun8978, rightways, ljwn357, Assassino9931

Solution

This post has been edited 1 time. Last edited by Tintarn, Mar 26, 2023, 7:00 AM

Z K Y

The post below has been deleted. Click to close.

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

seojun8978

73 posts

seojun8978

#4 h Mar 26, 2023, 6:57 AM • 1 Y

Y by Tintarn

Tintarn wrote:

Solution

Nice Solution!! It's like 20 times shorter than my solution.
But.. Do you mean except?(expect)

Z K Y

The post below has been deleted. Click to close.

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

qwedsazxc

167 posts

qwedsazxc

#5 h Mar 26, 2023, 6:58 AM

Y by

This was the easiest one on the test, probably everyone solved this.

Z K Y

The post below has been deleted. Click to close.

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

seojun8978

73 posts

seojun8978

#6 h Mar 26, 2023, 6:59 AM • 1 Y

Y by GuvercinciHoca

qwedsazxc wrote:

This was the easiest one on the test, probably everyone solved this.

Yes it's true. This would have been easier than geometry if there was one.

Z K Y

The post below has been deleted. Click to close.

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

Seungjun_Lee

526 posts

Seungjun_Lee

#7 h Mar 26, 2023, 1:50 PM

Y by

seojun8978 wrote:

qwedsazxc wrote:

This was the easiest one on the test, probably everyone solved this.

Yes it's true. This would have been easier than geometry if there was one.

I think the geometry problem was as easy as this and maybe a little easier(on day 1)

This post has been edited 2 times. Last edited by Seungjun_Lee, Mar 26, 2023, 1:51 PM

Z K Y

The post below has been deleted. Click to close.

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

pokmui9909

185 posts

pokmui9909

#8 h Mar 26, 2023, 1:54 PM

Y by

I'm very curious about the prize cut. I heard there are a lot of participants who solved $4, 5$ problems.

Z K Y

The post below has been deleted. Click to close.

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

Seungjun_Lee

526 posts

Seungjun_Lee

#9 h Mar 26, 2023, 1:57 PM

Y by

pokmui9909 wrote:

I'm very curious about the prize cut. I heard there are a lot of participants who solved $4, 5$ problems.

I did not take the test but it seems that 2 problems are given
Maybe really perfect 2problems or just 3problems will be honorable mention award

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5005 posts

IAmTheHazard

#10 h Mar 26, 2023, 3:39 PM • 2 Y

Y by megarnie, centslordm

Trivial by Zsigmondy

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9045 posts

Tintarn

#11 h Mar 26, 2023, 4:04 PM

Y by

IAmTheHazard wrote:

Trivial by Zsigmondy

I agree that the problem is trivial and my first thought when I saw the problem was also Zsigmondy, but now I am quite certain that there is no detailed solution with Zsigmondy that is shorter than my elementary one in #3. (After all, there is no way around checking the small cases.)

This post has been edited 1 time. Last edited by Tintarn, Mar 26, 2023, 5:14 PM

Z K Y

The post below has been deleted. Click to close.

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

rightways

868 posts

rightways

#12 h Mar 26, 2023, 5:05 PM

Y by

$Lemma:$

If $n>1$ , then the greatest prime divisor of $2^n-1$ is greater than the greatest prime divisor of $n$ .

Proof:

Let $p|n$ is greatest prime divisor of $n$ , then for some prime $q$ :
$q|2^p-1|2^n-1$ , then $q>p$ because $p=ord_2(q)$ . But $q$ is also a divisor of $2^n-1$ , so it is not greater than gpd of $2^n-1$ .

Now, in problem, by lemma we have that $7$ is greater than any prime divisor of $n$ , so we can write $n=2^a3^b5^c$ and we can easily finish problem by proving this $c<1$ and $b<2$ and $a<3$

Z K Y

The post below has been deleted. Click to close.

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

rightways

868 posts

rightways

#13 h Mar 26, 2023, 5:13 PM

Y by

Can you post KJMO day 2 problems?

qwedsazxc wrote:

Find all positive integers $n$ satisfying the following.
$2^n-1 \text{ doesn't have a prime factor larger than } 7$

Z K Y

The post below has been deleted. Click to close.

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

qwedsazxc

167 posts

qwedsazxc

#14 h Mar 27, 2023, 7:49 AM

Y by

rightways wrote:

Can you post KJMO day 2 problems?

qwedsazxc wrote:

Find all positive integers $n$ satisfying the following.
$2^n-1 \text{ doesn't have a prime factor larger than } 7$

There isn't a KJMO day 2. Final KMO contestants are picked from the people who excelled KMO 2nd round or KJMO 2nd round. I had the chance to take the Final KMO because I got a silver award from the KJMO I took on November 2022.

Z K Y

The post below has been deleted. Click to close.

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

hectorleo123

347 posts

hectorleo123

#15 h May 18, 2023, 12:12 AM

Y by

qwedsazxc wrote:

Find all positive integers $n$ satisfying the following.
$2^n-1 \text{ doesn't have a prime factor larger than } 7$

$2^2-1=2$
$2^3-1=7$
$2^4-1=3\times 5$
$gcd(2,1)=1$
By Zsigmondy's Theorem:
$\Rightarrow \exists$ prime $p \neq 2,3,5,7 / p|2^n-1, \forall n>4$
$\Rightarrow n\le 4$
But there is an exception $n=6$
$\Rightarrow n=1,2,3,4$ and $6$ are the only values that satisfy the condition $_\blacksquare$

This post has been edited 1 time. Last edited by hectorleo123, May 19, 2023, 1:48 AM

Z K Y

The post below has been deleted. Click to close.

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

Aiden-1089

302 posts

Aiden-1089

#16 h Mar 26, 2024, 4:31 AM

Y by

It is easy to check that $n=1,2,3,4,6$ works. We claim that these are the only solutions.
Clearly $2 \nmid 2^n-1$ . By Zsigmondy's theorem, any other $n$ would lead to $2^n-1$ having a prime divisor $p$ where $p \neq 3$ (because $3 \mid 2^2-1$ ), $5$ (because $5 \mid 2^4-1$ ), $7$ (because $7 \mid 2^3-1$ ). Since $p>7$ , $n$ does not satisfy the condition.

This post has been edited 1 time. Last edited by Aiden-1089, Mar 26, 2024, 4:32 AM

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

650 posts

cursed_tangent1434

#17 h May 10, 2024, 2:33 PM • 1 Y

Y by GeoKing

Me when this actually appeared on our National Olympiad. We claim that the only answers are $2,3,4$ and $6$ . It is easy to see that these solutions indeed work. Now, we show that there are no other solutions.

We use the well known lemma that for all $d\mid n$ for positive integers $n$ ,
$a^d - b^d \mid a^n - b^n$ for all positive integers $a,b$ extensively through out this solution. We first constrict the divisors of $n$ .

Claim : There exists no prime divisor $p >3$ of $n$ .
Proof : Say there exists such a prime factor $p$ of $n$ . Then,
$2^p -1 \mid 2^n-1$ and since $2^n-1$ has no prime factor larger than 7, this implies that $2^p-1$ also satisfies the same property. But, it is easy to see that $2 \nmid 2^n-1$ for any $n$ , $3\mid 2^n-1$ only for even $n$ , $5\mid 2^n-1$ only for $4\mid n$ and $7\mid 2^n-1$ only for $3\mid n$ . Since $p>3$ , this means that none of these prime factors can divide $2^p-1$ implying that it has a prime factor larger than 7, which is a clear contradiction. This proves the claim.

Now, we also note that,
$2^8-1 = 255=3 \times 5 \times 17$ so, $8 \nmid n$ (since then $17 \mid 2^n-1$ ), and also
$2^9 -1 = 511 = 7 \times 73$ so $9 \nmid n$ as well. This implies that $12 \mid n$ so $n \in \{1,2,3,4,6,12\}$ . Now, we can simply check all these possibilities and see that they all work except for $1$ (which we exclude for conventional reasons) and $12$ (which we exclude since $2^{12}-1= 3^2 \times 5 \times 7 \times 13$ so $13$ is a prime factor), which implies that the solution set is indeed as claimed.

Z K Y

The post below has been deleted. Click to close.

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

kub-inst

31 posts

kub-inst

#18 h Jun 3, 2024, 12:21 PM

Y by

If $n$ satisfies the limit, then we can let $2^n-1=3^a\cdot 5^b\cdot 7^c$
Since $3||(2^2-1),$ $5||(2^4-1),$ $7||(2^3-1)$ Then through LTE we can know that :
If $2|n,a=v_3(2^n-1)=v_3(\frac n2)+1\leq \log_3\frac n2+1.$
If $4|n,b=v_5(2^n-1)=v_5(\frac n4)+1\leq \log_5\frac n4+1.$
If $3|n,c=v_7(2^n-1)=v_7(\frac n3)+1\leq \log_7\frac n3+1.$
Hence, $2^n-1=3^a\cdot 5^b\cdot 7^c\leq 3^{\log_3\frac n2+1}\cdot 5^{\log_5\frac n4+1}\cdot 7^{\log_7\frac n3+1}=\frac{85n^3}{24}$ (If $a, b$ or $c=0$ , the inequality above is still ture evidently.)
Since $n\in \mathbb{N}^+,$ the inequality above requires $n\leq12$ .
We can verify that the original statement is TRUE only when $n=1,2,3,4,6$ . $\square$

This post has been edited 1 time. Last edited by kub-inst, Jun 5, 2024, 6:03 AM
Reason: mistyped

Z K Y

The post below has been deleted. Click to close.

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

Scilyse

387 posts

Scilyse

#20 h Dec 28, 2024, 3:51 PM

Y by

Zsigmondeez nuts

Z K Y

The post below has been deleted. Click to close.

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

Eka01

204 posts

Eka01

#21 h Jan 8, 2025, 6:04 PM

Y by

By Zsigmondy, every $n$ gives a new prime factor apart from a small few (like greater than 10 or smth, dont have the energy to recall the edge cases). Then just check the few cases by hand.

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

400 posts

alexanderhamilton124

#22 h Jan 8, 2025, 6:07 PM

Y by

7 | 2^3 - 1 ==> we done by zsigmondy

This post has been edited 1 time. Last edited by alexanderhamilton124, Jan 9, 2025, 3:34 AM

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4243 posts

RedFireTruck

#24 h Jan 8, 2025, 7:58 PM

Y by

n=1 gives 1
n=2 gives 3
n=3 gives 7
n=4 gives 15=3*5
n=6 gives 63=3*3*7

by zsigmondy theorem, every other 2^n-1 must have a prime factor other than 3,5,7 so this is all

Z K Y

The post below has been deleted. Click to close.

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

Ihatecombin

69 posts

Ihatecombin

#25 h Jan 13, 2025, 10:50 AM

Y by

L.T.E also works here, even with brain dead level bounding one only needs to check until $n=14$ .

Z K Y

The post below has been deleted. Click to close.

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

Giant_PT

50 posts

Giant_PT

#26 h Apr 22, 2025, 3:40 PM

Y by

Almost trivial by Zsigmondy

We can see that the smallest $n$ for which $3|2^{n}-1$ , $5|2^{n}-1$ , and $7|2^{n}-1$ are $2$ , $4$ and $3$ respectively. Also, we have the exceptional case when $n=6$ , so by just checking small values of $n$ , we see that $n=1,2,3,4,6$ are the only solutions.

This post has been edited 2 times. Last edited by Giant_PT, Apr 22, 2025, 3:41 PM
Reason: Typos

Z K Y

The post below has been deleted. Click to close.

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

Assassino9931

1378 posts

Assassino9931

#27 h May 27, 2025, 2:57 PM

Y by

Here is a solution with very elementary methods only.

Direct verification shows that $n=1,2,3,4,6$ work and $n=5,7$ do not. We prove that no $n\geq 8$ works.

Note that $2^n - 1$ is divisible by $3$ if and only if $n$ is even, divisible by $5$ if and only if $n$ is a multiple of $4$ , and divisible by $7$ if and only if $n$ is a multiple of $3$ . Suppose $n$ is odd - then $2^n - 1 = 7^t$ , which is impossible for $n\geq 4$ by mod $16$ .

Hence $n$ is even. If $2^n - 1$ is divisible by all of $3,5,7$ , then $n$ is divisible by $12$ , but then $13$ divides $2^{n} - 1$ by Fermat, contradiction. Hence $2^n - 1 = 3^a, 5^a, 3^a5^b$ or $3^a7^b$ . The first two are impossible by mod $8$ (the second one even by mod $4$ ). For $2^n - 1 = 3^a5^b$ , $a,b > 0$ , we must have $n=4t, t \geq 2$ and then $(2^t - 1)(2^t + 1)(2^{2t} + 1) = 3^a5^b$ where the factors on the left are pairwise coprime - hence at least one of them equals $1$ , impossible for $t\geq 2$ . Finally, for $2^n - 1 = 3^a7^b$ we have $n=6t$ where $t\geq 3$ is odd (as $12$ does not divide $n$ by above), and then $(2^t - 1)(2^{t} + 1)(2^{2t} + 2^t + 1)(2^{2t} - 2^t + 1) = 3^a7^b$ , with the first three factors being pairwise coprime (only the second one is divisible by $3$ for odd $t$ ), hence one of them equals $1$ , impossible for $t\geq 3$ .

Z K Y