funny title placeholder

The post below has been deleted. Click to close.

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

pikapika007

297 posts

pikapika007

#1 h Friday at 12:10 PM

Y by

Let $S$ be a set of integers with the following properties:

$\{ 1, 2, \dots, 2025 \} \subseteq S$ .
If $a, b \in S$ and $\gcd(a, b) = 1$ , then $ab \in S$ .
If for some $s \in S$ , $s + 1$ is composite, then all positive divisors of $s + 1$ are in $S$ .

Prove that $S$ contains all positive integers.

This post has been edited 1 time. Last edited by pikapika007, Friday at 12:12 PM
Reason: wrong year

Z K Y

The post below has been deleted. Click to close.

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

bjump

987 posts

bjump

#2 h Friday at 12:13 PM

Y by

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

Z K Y

The post below has been deleted. Click to close.

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

TaurusJ

322 posts

TaurusJ

#3 h Friday at 12:14 PM

Y by

Tried doing primitive roots for 3 hours and couldn’t get it did I overthink this question…

Z K Y

The post below has been deleted. Click to close.

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

littlefox_amc

20 posts

littlefox_amc

#4 h Friday at 12:17 PM

Y by

xook i’m banned

This post has been edited 1 time. Last edited by littlefox_amc, Friday at 12:28 PM

Z K Y

The post below has been deleted. Click to close.

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

bachkieu

130 posts

bachkieu

#5 h Friday at 12:19 PM

Y by

assume we can get all $n \leq k$ , we just want to show that $k + 1 \in S$
if $k+1$ composite spam rule #2
if $k+1$ is prime, consider prime $\sqrt[3]{k} < p < \sqrt{k}$ such that $k + 1 \not \equiv 1 \pmod p$
letting $a$ be inverse of $k + 1$ 's residue class we can construct $(k+1)a-1 \in S$ so we get $(k+1) | a(k+1)$ also in $S$

This post has been edited 1 time. Last edited by bachkieu, Friday at 8:30 PM

Z K Y

The post below has been deleted. Click to close.

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

BS2012

935 posts

BS2012

#6 h Friday at 12:23 PM • 1 Y

Y by bachkieu

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

$2p-1$ works for fermat primes but i didnt realize that :wallbash_red:

how many pts for proving everything except having a sort of botched proof for fermat primes

This post has been edited 2 times. Last edited by BS2012, Friday at 12:28 PM

Z K Y

The post below has been deleted. Click to close.

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

miguel00

584 posts

miguel00

#7 h Friday at 12:28 PM

Y by

BS2012 wrote:

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

Yes I thought that also but couldn't solve the problem. I sort of have a feeling this problem can be solved with Dirichlet's Theorem on Arithmetic Progression.

Z K Y

The post below has been deleted. Click to close.

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

bjump

987 posts

bjump

#8 h Friday at 12:31 PM

Y by

BS2012 wrote:

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

i think mine still works tho?? ill ask my proctor for my scans back.
bc if p+1 is 2^x, we have 2^x-1 is not divis by 3 so x is odd i showed you can construct 2^(x+1) by multiplying 2^{(x+1)/2}-1, and 2^{(x+1)/2}+1, and if p-1 = 2^x x is even, i showed how we can let x = 2h then we can use 2^(h+1)-1 and 2^(h+1)+1 to make 2^(2h+2)-1 to make 2^(2h+2) to make 2^(2h+1), we have 2h+1 = v2(p^2-1) so we can get p^2-1 so we can get p^2 to get p. This works because 2025 is sufficiently large. non powers of 2 work more easily

Z K Y

The post below has been deleted. Click to close.

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

KevinChen_Yay

204 posts

KevinChen_Yay

#9 h Friday at 12:31 PM

Y by

how many points for only doing composite :maybe:

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5538 posts

megarnie

#10 h Friday at 12:33 PM • 2 Y

Y by MS_asdfgzxcvb, KevinChen_Yay

Suppose otherwise. First note for any pairwise relatively prime set of integers in $S$ , their product is in $S$ .

Claim: $S$ contains infinitely many primes
Proof: Let $\{p_i\}_{i=1}^k$ be the odd primes in $S$ , where $p_1 = 3$ . Note that $\prod_{i=1}^k p_i + 1$ is composite, so all of its prime divisors must be in $S$ , so it's a power of $2$ . Similarly, $9\prod_{i=2}^k p_i + 1$ is composite and in $S$ and thus is a power of $2$ , which is bad by mod $4$ . $\square$

Let $p$ be the smallest number not in $S$ . Note that $p$ is prime. By PHP there exist infinitely many primes over $p - 1$ in $S$ that are $r \pmod p$ for some residue $r \ne 0$ . Multiplying $p - 1$ of them together and then multiplying this by $p - 1$ gives that something large enough that is $-1 \pmod p$ is in $S$ and adding by $1$ gives that $p \in S$ , absurd, so we are done.

This post has been edited 18 times. Last edited by megarnie, Yesterday at 6:15 PM

Z K Y

The post below has been deleted. Click to close.

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

bjump

987 posts

bjump

#11 h Friday at 12:34 PM

Y by

bjump wrote:

BS2012 wrote:

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

i think mine still works tho?? ill ask my proctor for my scans back.
bc if p+1 is 2^x, we have 2^x-1 is not divis by 3 so x is odd i showed you can construct 2^(x+1) by multiplying 2^{(x+1)/2}-1, and 2^{(x+1)/2}+1, and if p-1 = 2^x x is even, i showed how we can let x = 2h then we can use 2^(h+1)-1 and 2^(h+1)+1 to make 2^(2h+2)-1 to make 2^(2h+2) to make 2^(2h+1), we have 2h+1 = v2(p^2-1) so we can get p^2-1 so we can get p^2 to get p. This works because 2025 is sufficiently large. non powers of 2 work more easily

can someone verify this??

Z K Y

The post below has been deleted. Click to close.

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

BS2012

935 posts

BS2012

#12 h Friday at 12:35 PM

Y by

BS2012 wrote:

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

$2p-1$ works for fermat primes but i didnt realize that :wallbash_red:

how many pts for proving everything except having a sort of botched proof for fermat primes

uh can someone pls give an estimate of how many pts this would get

Z K Y

The post below has been deleted. Click to close.

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

bachkieu

130 posts

bachkieu

#13 h Friday at 12:38 PM

Y by

I think $\leq 5$ ???

Z K Y

The post below has been deleted. Click to close.

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

BS2012

935 posts

BS2012

#14 h Friday at 12:39 PM

Y by

bachkieu wrote:

I think $\leq 5$ ???

ik its <=5 i just need to know if 5 is possible or if i should expect a 0+

Z K Y

The post below has been deleted. Click to close.

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

bjump

987 posts

bjump

#15 h Friday at 12:41 PM

Y by

miguel00 wrote:

BS2012 wrote:

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

fails for mersenne and fermat primes though

Yes I thought that also but couldn't solve the problem. I sort of have a feeling this problem can be solved with Dirichlet's Theorem on Arithmetic Progression.

bruh asdfjkl i found a finish for that tho,

Z K Y

The post below has been deleted. Click to close.

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

andliu766

108 posts

andliu766

#40 h Friday at 3:46 PM

Y by

Haven't found anyone else with this solution, so it might be fakesolve :wacko:

FTSOC, let $p$ be smallest integer not in $S$ . Clearly, $p$ must be prime, and $p > 2025$ .
By Bertrands, let $\frac p2 < q < p$ be prime. If $q_1 \equiv - \frac 1q \pmod{p}$ , then either $\gcd(q,q_1) = 1$ or $q=q_1$ . If former, then we are done. Otherwise $q^2 \equiv (p-q)^2 -1 \pmod{p}$ , and $p \equiv 1 \pmod{4}$ .
Then, let $m$ be prime between $\frac p4$ and $\frac p2$ . Define $m_1$ similar to above. Similarly, $\gcd(m,m_1)=1$ so we're done, or $m_1 = m,2m,3m$ .
If $m_1=m$ , then $m^2\equiv -1\pmod{p}$ , which is impossible since $m = q$ and $m = p-q$ .
If $m_1 = 2m$ , then $(p-2m)(p-m)$ is $-1 \pmod{p}$ , and $\gcd(p-2m,p-m)=\gcd{p,m}=1$ , so $p$ belongs in $S$
If $m_1=3m$ , then $p^2 \equiv -\frac{1}{3} \pmod {3}$ . Using Legendre symbol, we get $1 = \binom{\frac{-1}{3}}{p} = \binom{-3}{p} = \binom{-1}{p}\binom{3}{p}=\binom{3}{p} = \binom{p}{3}$ , using the fact that $p \equiv 1 \pmod{4}$ twice. This implies that $p \equiv 1 \pmod{3}$ . Then, $(p-2)(\frac{p+1}{2})=p(\frac{p-1}{2})-1$ and $\gcd(p-2,\frac{p+1}{2}) = \gcd(p-2,3)$ , which is $1$ by $p \equiv 1 \pmod{3}$ . Thus $p$ is in $S$ .

In all cases, $p$ is in $S$ , 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.

Martin2001

131 posts

Martin2001

#41 h Friday at 3:49 PM

Y by

p-1, p+1
if that don't work it's either 2p-1 for the prime is 2^n+1 and 3p-1 for the prime being 2^n-1 by mod 3 and mod 4, respectively.

Z K Y

The post below has been deleted. Click to close.

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

Martin2001

131 posts

Martin2001

#42 h Friday at 4:03 PM

Y by

wow am I unintelligible I am sorry for causing a stroke for any of yall who read that

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7308 posts

DottedCaculator

#43 h Friday at 4:04 PM • 1 Y

Y by Pengu14

oops wrong

This post has been edited 1 time. Last edited by DottedCaculator, Friday at 4:41 PM

Z K Y

The post below has been deleted. Click to close.

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

OmenOrNot

8 posts

OmenOrNot

#44 h Friday at 4:27 PM

Y by

bjump wrote:

u can get 1->p-1
then use v2 casework on p-1 and p+1 to show you can get p^2-1 -> p^2-> p then get up to the next prime -1. you win

Exactly my sol but I realized it doesn’t work for Fermat and mersenne primes lmao is that like a 5 or

Z K Y

The post below has been deleted. Click to close.

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

VulcanForge

626 posts

VulcanForge

#45 h Friday at 5:03 PM • 1 Y

Y by bjump

Solved with awang11

Assume otherwise, and look at the smallest missing number; clearly it must be a prime $p > 2025$ . Let $4^k$ be the smallest power of four larger than $p$ .

Claim: All divisors of $4^k$ are in $S$ .

Proof. Since $2^k+1 < 4^{k-1} < p$ , we have that the numbers $2^k \pm 1$ are less than $p$ (hence in $S$ ) and relatively prime. Hence the product $(2^k-1)(2^k+1) = 4^k-1$ is in $S$ , which then generates all divisors of $4^k$ as desired.

Now consider the numbers $\tfrac{p-1}{\nu_2(p-1)}$ and $\tfrac{p+1}{\nu_2(p+1)}$ , which are less than $p$ (hence in $S$ ) and relatively prime. Exactly one of $\nu_2(p-1)$ and $\nu_2(p+1)$ is $1$ , and since $p+1 \neq 4^k$ (because the latter is $1 \pmod{3}$ ) both of them are at most $2k-1$ . Hence
$\nu_2(p^2-1) = \nu_2(p-1) + \nu_2(p+1) \le 1 + (2k-1) = 2k \implies 2^{\nu_2(p^2-1)} \in S$ by the claim. Now the relatively-prime generation rule gives
$\left( \frac{p-1}{\nu_2(p-1)}, \frac{p+1}{\nu_2(p+1)}, 2^{\nu_2(p^2-1)} \right) \implies p^2-1 \in S$ which consequently generates $p$ , contradiction.

This post has been edited 2 times. Last edited by VulcanForge, Friday at 5:07 PM

Z K Y

The post below has been deleted. Click to close.

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

dragoon

1921 posts

dragoon

#46 h Friday at 5:37 PM

Y by

andliu766 wrote:

Haven't found anyone else with this solution, so it might be fakesolve :wacko:

FTSOC, let $p$ be smallest integer not in $S$ . Clearly, $p$ must be prime, and $p > 2025$ .
By Bertrands, let $\frac p2 < q < p$ be prime. If $q_1 \equiv - \frac 1q \pmod{p}$ , then either $\gcd(q,q_1) = 1$ or $q=q_1$ . If former, then we are done. Otherwise $q^2 \equiv (p-q)^2 -1 \pmod{p}$ , and $p \equiv 1 \pmod{4}$ .
Then, let $m$ be prime between $\frac p4$ and $\frac p2$ . Define $m_1$ similar to above. Similarly, $\gcd(m,m_1)=1$ so we're done, or $m_1 = m,2m,3m$ .
If $m_1=m$ , then $m^2\equiv -1\pmod{p}$ , which is impossible since $m = q$ and $m = p-q$ .
If $m_1 = 2m$ , then $(p-2m)(p-m)$ is $-1 \pmod{p}$ , and $\gcd(p-2m,p-m)=\gcd{p,m}=1$ , so $p$ belongs in $S$
If $m_1=3m$ , then $p^2 \equiv -\frac{1}{3} \pmod {3}$ . Using Legendre symbol, we get $1 = \binom{\frac{-1}{3}}{p} = \binom{-3}{p} = \binom{-1}{p}\binom{3}{p}=\binom{3}{p} = \binom{p}{3}$ , using the fact that $p \equiv 1 \pmod{4}$ twice. This implies that $p \equiv 1 \pmod{3}$ . Then, $(p-2)(\frac{p+1}{2})=p(\frac{p-1}{2})-1$ and $\gcd(p-2,\frac{p+1}{2}) = \gcd(p-2,3)$ , which is $1$ by $p \equiv 1 \pmod{3}$ . Thus $p$ is in $S$ .

In all cases, $p$ is in $S$ , so we are done.

I basically did that please give me points :pray:

Z K Y

The post below has been deleted. Click to close.

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

llddmmtt1

392 posts

llddmmtt1

#47 h Friday at 7:21 PM

Y by

someone check my sol

induction. composite is trivial so get p, assuming 1,2,...,p-1 in s.
let p/2<q<p, qr=-1 mod p
if q\ne r then gcd(q,r)=1 so you get qr, then p|qr+1 and ur done
if q=r then q^2=-1 mod p, then q(q+p) mod p. you now want p+q in s
if p+q is a power of 2, notice 2^k-1, 2^k+1 gives 2^(2k)
if p+q not a power of 2, do 2^v_2(p+q) and (p+1)/2^v_2(p+q)

also another skibidi solution is p/2<q,r<p, then q^2=-1 and r^2=-1 are both impossible so at least one of them works, but idk how to prove that there are two primes between p/2 and p

Z K Y

The post below has been deleted. Click to close.

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

aliz

156 posts

aliz

#48 h Yesterday at 5:23 AM

Y by

Everything in red is stuff I definitely not write during the contest

Assume contradiction, then let p be the smallest positive integer not in S.

Claim 1: p is prime
Proof: Since 2023 < p-1 and p-1 < p, p-1 is in S, therefore if p is composite then it is in S.

Claim 2: For integer a>1 I may have done a > 0, ap - 1 is not in S
Proof: If it is, ap is composite so all of its divisors, including p, are in S.

Setting a = p in Claim 2 gives that p^2 - 1 must not be in S. Now we split into cases.

Case 1: p = 1 mod 4
Proof 1:
(1/2): We will first show p = 2^k + 1 for some positive integer k.

Factor p^2 - 1 = (1/2 * (p+1)) * (2 * (p-1)), then notice gcd(1/2 * (p+1), 2 * (p-1)) | 2gcd(p-1, p+1) | 4 but 1/2 * (p+1) is odd so the numbers are coprime.
1/2 * (p+1) < p so if 2 * (p-1) is also in S we have contradiction. Let 2 * (p-1) = 2^a * b where 2^a and b are positive integers and b is odd. Now 4|p-1 so 8|2(p-1), 2^a >= 8. This means b = 2 / 2^a * (p-1) <= 1/4 * (p-1) < p. If b >= 3, 2 * (p-1) / b <= 2/3 * (p-1) < p. Therefore b < 3. b is odd so b = 1, therefore 2 * (p-1) = 2^a, and since a > 5 this means p = 2^(a-1) + 1 and this is 1 mod 4.

(2/2): Now consider a = 5 in claim 2 to get 5p-1. 5p-1 = 5-1 = 0 mod 4 (I believe here I mentioned bounding and then wrote something along the lines of v_3(5p-1) = 1 and (5p-1) - (2p-1) = [i forgot the exact thing]).

First notice 5p-1 cannot be a power of 2 because of bounding (p-1 is a power of 2, but 4(p-1) < 5p-1 < 8(p-1) since p > 2025). If 5p-1 = 3 * 2^k, then 3p-3 is also 3 times a power of 2, but 3p-3 < 5p-1 < 6p-6. If 5p-1 = 4 * q for a prime q, then notice 2^k + 1 =/ 0 mod 3 so p must equal 2 mod 3, which yields 3 | q (obviously q > 3).

We can prove 5p-1 must take this form. Let 5p-1 = 2^a * b where b is odd and a, b are positive integers. If 2^a >= 8 and b is not equal to 1 or 3, b cannot equal 2, or 4 other, so b >= 5. Now b = (5p-1) / 2^a <= (5p-1) / 8 < p and 2^a = (5p-1) / b <= (5p-1) / 5 < p.

If 2^a = 4 and b is not prime, let b = b_1 * b_2 for coprime b_1, b_2 both greater than 1. Then b_1 > 3 and b_2 > 3, so b_1 and b_2 >= 5. Now 4 * b_1 * b_2 = 5p - 1 so b_2 = (5p-1) / 4b_1 < (5p-1) / 5 < p and b_1 = (5p-1) / b_2 < (5p-1) / 5 < p.

Notice that in all cases if 5p-1 does not take this form we reach a contradiction.

Case 2: p = 3 mod 4
Proof 2:
(1/2): We will first show p = 2^k - 1 for some positive integer k.

p^2 - 1 = (1/2 * (p-1)) * (2 * (p+1)), again 1/2 * (p-1) is odd and the terms are coprime, let
2 * (p+1) = 2^a * b for positive integers a, b with odd b, a >= 3 so b <= 2/8 * (p+1) < p and if b >= 3 then 2^a <= 2/3 * (p+1) < p, so b = 1 and since a > 5 we have 2 * (p+1) = 2^a, so p = 2^(a-1) - 1 so
p = 2^k - 1.

(2/2): Consider a = 3 in claim 2, or 3p-1. Now notice 4|3p-1. If 3p-1 = 2^a * b for odd positive integer b and positive integer a and b =/ 1, then b >= 3 (b can't be 2) we have 2^a = (3p-1)/b < (3p-1)/3 < p, and remember that b = (3p-1)/2^a <= (3p-1)/4 < p. Therefore b = 1 so 3p-1 is a power of 2. But p+1 is a power of 2 and 2p+2 < 3p-1 < 4p+4 by bounding so we are done.

So p is not 1 mod 4 or 3 mod 4 and it is prime, but it is larger than 2025, so p cannot exist. Thus we have proven our desired statement by contradiction.

This post has been edited 1 time. Last edited by aliz, Yesterday at 5:25 AM

Z K Y

The post below has been deleted. Click to close.

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

llddmmtt1

392 posts

llddmmtt1

#49 h Yesterday at 12:39 PM • 1 Y

Y by megarnie

"1 mod 4 or 3 mod 4"
what the 1434

This post has been edited 1 time. Last edited by llddmmtt1, Yesterday at 12:39 PM
Reason: what the typo

Z K Y

The post below has been deleted. Click to close.

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

ReaperGod

1577 posts

ReaperGod

#50 h Yesterday at 2:42 PM

Y by

vincentwant wrote:

How many points would I get taken off for this:

Let 1 to p-1 in S. Let p/2<c<p be prime. Then c divided one of p-1, 2p-1, 3p-1, etc up to (c-1)p-1. It cannot be p-1 bc size. Then let c divide gp-1. Then (gp-1)/c and c are both in S, so then (this is the error) gp-1 is in S. Thus p is in S.

I missed the case where c^2 divides gp-1. However this case is fine because size gives c^2=gp-1 and c^2-1 is easy to show to be in S (consider $(c\pm1)/2$ ), but I didn't have time to find this in contest as I found the error in the last 10 min oops

Edit: this doesn't actually work, but just choosing another c I think guarantees that it can't happen again

That is exactly what I did. Could someone confirm that it is considered well known that there are two primes between n/2 and n for large n?

Z K Y

The post below has been deleted. Click to close.

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

vincentwant

1263 posts

vincentwant

#51 h Yesterday at 3:41 PM

Y by

ReaperGod wrote:

vincentwant wrote:

How many points would I get taken off for this:

Let 1 to p-1 in S. Let p/2<c<p be prime. Then c divided one of p-1, 2p-1, 3p-1, etc up to (c-1)p-1. It cannot be p-1 bc size. Then let c divide gp-1. Then (gp-1)/c and c are both in S, so then (this is the error) gp-1 is in S. Thus p is in S.

I missed the case where c^2 divides gp-1. However this case is fine because size gives c^2=gp-1 and c^2-1 is easy to show to be in S (consider $(c\pm1)/2$ ), but I didn't have time to find this in contest as I found the error in the last 10 min oops

Edit: this doesn't actually work, but just choosing another c I think guarantees that it can't happen again

That is exactly what I did. Could someone confirm that it is considered well known that there are two primes between n/2 and n for large n?

yes (from wikipedia)

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

llddmmtt1

392 posts

llddmmtt1

#52 h Yesterday at 4:42 PM

Y by

i thought you had to say the name of a theorem if you wanted to use it, as this is not like extremely well known

Z K Y

The post below has been deleted. Click to close.

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

MathLuis

1464 posts

MathLuis

#54 h Today at 1:01 AM

Y by

This kind of qns has been getting more popular lately, kinda fun I'd say.
We prove by induction that if $\{1,2 \cdots ,n \} \in S$ then $n+1 \in S$ , this is clear if $n+1$ is composite so assume that $n+1$ is prime.
Now we will prove that $2^{\ell \cdot 2^k} \pm 1, 2^{\ell \cdot 2^k}$ are all on $S$ for all positive integers $k$ and $\ell=3,5$ (because $2025$ is smol :c), base cases are given and for the inductive step just note that $\gcd(2^{\ell \cdot 2^k}-1, 2^{\ell \cdot 2^k}+1)=1$ and therefore $2^{\ell \cdot 2^{k+1}}-1 \in S$ and also then $2^{\ell \cdot 2^{k+1}} \in S$ but also note that $2^{2^{k+1}}+1 \mid 2^{\ell \cdot 2^{k+1}}+1$ so it can't be prime therefore it is also in $S$ thus claim proven.
Now clearly because $k$ can be made large enough from here we get that all powers of $2$ are on $S$ , notice then as well that from here we get that $2^x+1 \in S$ for all $x$ composite and that posses one odd factor but then considering the rest of divisors of this amount by making $x$ have a lot of factors we have that all $2^x+1 \in S$ for all positive integers $x$ and using trivial induction from here. we can also get that $2^x-1 \in S$ for all positive integers $x$ and thus we also have $2^x-2 \in S$ for all positive integers $x$ using condition 1 and thus using condition 2 now here consider some large enough composite $x$ then all positive divisors of $2^x-1$ are on $S$ as well so by setting $p-1 \mid x$ for $p$ odd prime and FLT we get that all primes are on $S$ but also by taking $(p-1) p^{\ell} \mid x$ and using euler theorem we get that all odd prime powers are on $S$ as well and well this is kinda overkill since all we needed was $n+1$ prime to be on $S$ so that induction is complete as well xD, thus we are done :cool:

.

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6869 posts

v_Enhance

#55 h Today at 1:36 AM

Y by

Solution from Twitch Solves ISL:

We prove by induction on $N$ that $S$ contains $\{1, \dots, N\}$ with the base cases being $N = 1, \dots, 2025$ already given.
For the inductive step, to show $N+1 \in S$ :

If $N+1$ is composite we're already done from the third bullet.
Otherwise, assume is an (odd) prime number. We say a number is good if the prime powers in its prime factorization are all less than $p$ . Hence by the second bullet (repeatedly), good numbers are in $S$ . Now our proof is split into three cases:
1. Suppose neither $p-1$ nor $p+1$ is a power of $2$ (but both are still even). We claim that the number $s \coloneq p^2-1 = (p-1)(p+1)$ is good. Indeed, one of the numbers has only a single factor of $2$ , and the other by hypothesis is not a power of $2$ (but still even). So the largest power of $2$ dividing $p^2-2$ is certainly less than $p$ . And every other prime power divides at most one of $p-1$ and $p+1$ .
  Hence $s \coloneq p^2-1$ is good. As $s+1 = p^2$ , Case 1 is done.
2. Suppose $p+1$ is a power of $2$ ; that is $p = 2^q-1$ . Since $p > 2025$ , we assume $q \ge 11$ is odd. First we contend that the number $s' \coloneq 2^{q+1} - 1 = \left( 2^{(q+1)/2}-1 \right) \left( 2^{(q+1)/2}+1 \right)$ is good. Indeed, this follows from the two factors being coprime and both less than $p$ . Hence $s'+1 = 2^{q+1}$ is in $S$ .
  Thus, we again have $s \coloneq p^2-1 = (p-1)(p+1) \in S$ as we did in the previous case, because the largest power of $2$ dividing $p^2-1$ will be exactly $2^{q+1}$ which is known to be in $S$ . And since $s+1=p^2$ , Case 2 is done.
3. Finally suppose $p-1$ is a power of $2$ ; that is $p = 2^{2^e}+1$ is a Fermat prime. Then in particular, $p \equiv 2 \pmod 3$ . Now observe that $s \coloneq 2p-1 \equiv 0 \pmod 3$ and moreover $2p-1$ is not a power of $3$ (it would imply $2^{2^e+1} + 1 = 3^k$ , which is impossible for $k \ge 3$ by Zsigmondy/Mihailescu/etc.). So $s$ is good, and since $s = 3p$ , Case 3 is done.
Having finished all the cases, we conclude and the induction is done.

Remark: In fact just $2025 \in S$ is sufficient as a base case; however this requires a bit more work to check. Here is how:

From $2025 \in S$ we get $2026 = 2 \cdot 1013$ , so $2,1013 \in S$ .
From $1013+1 = 1014 = 2 \cdot 3 \cdot 13^2$ we get $3,13 \in S$ .
From $3+1 = 4$ we get $4 \in S$ .
$3 \cdot 13 + 1 = 40 = 2^3 \cdot 5$ we get $5 \in S$ .
Once $\{1,2,\dots,5\} \subseteq S$ , the induction above actually works fine; that is, $N \le 6$ are sufficient as base cases for the earlier cases to finish the rest of the problem. (Case 2 works once $q \ge 3$ , and Case 3 works once $e \ge 2$ .)

However, $\{1,2,3,4\} \subseteq S$ is not sufficient; for example $S = \{1,2,3,4,6,12\}$ satisfies all the problem conditions.

Z K Y