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

Tintarn wrote:

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

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

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.

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)

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

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

Trivial by Zsigmondy

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

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

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

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.

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$

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.

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.

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$

Zsigmondeez nuts

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.

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

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

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