[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 709 KB, 1800x1108, day_48.png [View same] [iqdb] [saucenao] [google]
10576533 No.10576533 [Reply] [Original]

[math]
\text{Let }S\text{ be a finite set of integers, each greater than 1. Suppose that for each}
\\
\text{integer }n\text{ there is some }s\in S\text{ such that }\gcd(s,n)=1\text{ or }\gcd(s,n)=s\text{. Show}
\\
\text{that there exist }s,t\in S\text{ such that }\gcd(s,t)\text{ is prime.}
[/math]

>> No.10576535

Previous Thread >>10571410

>> No.10576538

Marry me, I know you're single.

>> No.10576593

>>10576533
havent figured it out yet but gcd(a,b) = s is a partial order on [math]\mathbb{Z}[/math]. might be a good start

>> No.10576711

>>10576533
For each s in S there must be each prime factor of s in S, or for n|s we have gcd(s,n) = n. QED.

>> No.10577023

thinly veiled homework thread

>> No.10577027

>>10576533
S = {42, 55}
For n = 55, s = 42 (because the first option is satisfied, the second does not need to be satisfied)
For n = 42, s = 55 (ditto)
gcd(42, 55) = 1.
1 is not prime.

>> No.10577039

>>10577027
Your S does not satisfy the conditions. i.e. what happens if n=10, etc.

>> No.10577050

>>10577027
What about n=10?

>> No.10577428 [DELETED] 

>>10576533
Let S={4}
gcd(4,4)=4
4 is not prime.

>> No.10578046

>>10576711
Wouldn't you just need a q that is coprime to s?
If n|s then gcd(n,q)=1

>> No.10578058

>>10576533
if the question is wrong, how are people supposed to solve it?

Counterexample:
S = {4;9}

for n=4; you have s = 9 such as gcd(s,n) = 1

for n=9; you have s = 4 such as gcd(s,n)=1

but there are no s,t in S such as gcd(s,t) is prime (since all combinations give a gcd of 1 or 4 or 9, none of which are prime).

>> No.10578060

>>10577050
>>10577039
10 isn't in his set S, why are you talking about 10?

>> No.10578067

>>10578060
Because 10 is an integer. Don't know how to read, nigger?

>> No.10578080
File: 80 KB, 478x523, 1555226403735[1].png [View same] [iqdb] [saucenao] [google]
10578080

>>10578067

>> No.10578089

>>10577027
>>10578058
are you fucking retarded? n is an arbitrary integer, not necessarily in S dumbasses

>> No.10578093

>>10578058
What happens when n=6?
gcd(4,6) = 2 != 1 or 4
gcd(9,6) = 3 != 1 or 9

>> No.10578115

>>10576533
When is says “every integer n”, does it mean every integer is the set of all integers?

>> No.10578117

Is it all the same retard or did this particular question attract a bunch of idiots?

>> No.10578121

>>10578080
Why are brainlet meme posters always the dumbest ones?

>> No.10578125

>>10578093
>>10578089
>>10578067
>>10578060
>>10577039
I think n DOES have to be in S
Otherwise, in order to satisfy the condition, the set would have to contain the set of all prime numbers, because if it didn’t, you could multiply all numbers in the set together to get n, and there would be no element s in S such that gcd(n, s) = 1
And since the set is finite, this can’t be the case either

>> No.10578132

>>10578125
S={2} is good.

>> No.10578133

>>10578125
S could be any finite subset of the primes and it still works.

S= {pq,qr,rp} also works.
Have you even thought about the problem?

>> No.10578137

>>10578125
Yes then gcd would be the biggest s in S. Seems like you don't understand what gcd is nor how to read simple math notation in statement.

>> No.10578139 [DELETED] 

>>10578125
>you could multiply all numbers in the set together to get n, and there would be no element s in S such that gcd(n, s) = 1
Then gcd(n, s) = s. Why can't you just read the question fully before posting?

>> No.10578146

>>10578137
>>10578139
Sorry, didn’t see that part

>> No.10578147

>>10578125
>I think n DOES have to be in S
well it fucking doesn't you retarded nigger
if you can't even read a problem correctly, you should probably give up on trying to solve putnam problems

>> No.10578153

Is every Putnam thread this rude?

>> No.10578276

>>10578147
>>10578139
>>10578137
>>10578133
Imagine being this insufferable.

>> No.10578281

>>10578276
Hey fuck off guy
I said something stupid, it’s over now, let it die

>> No.10578284

>>10578281
No, it's annoying to see people do this shit. As if they were born with this knowledge and anyone who doesn't possess it is retarded.
You see this kind of behavior on other boards as well. It's cringe as fuck.
You made a logical mistake, they wanted an excuse to call someone stupid.

>> No.10578287

>>10578284
>You made a logical mistake
No he didn't

>> No.10578293

>>10578284
It’s not worth getting bootyblasted at people being jerks on a Korean smoke signaling forum

>> No.10578301

>>10578287
Doesn't change the point.

>>10578293
It's a problem on the entire Internet.

>> No.10578303

>>10576533
Do I read this correctly?
The conditions on S are such that every element of S must be prime number! Suppose there is a non prime number in S, call it s. Take any prime factor p of a. Then gcd(p,s)=p which is neither s nor 1.

So, take any element s of S, since it is prime gcd(s,s)=s is prime.

>> No.10578310

>>10578303
Well, I believe you’re correct that S must contain a prime number, but the question that there is SOME s in S such that gcd(n, s) = 1 or s, they don’t ALL have to satisfy it

>> No.10578313 [DELETED] 

>>10578310
Retarded nigger

>> No.10578317

>>10578303
>>10578310
I'm a brainlet.
If s and t are prime, with s ≠ t, wouldn't that mean the gcd would be 1, and therefore not a correct answer?
Or does t have some special meaning here that I don't understand? I'm only barely starting to learn about set theory.

>> No.10578322

>>10578317
Read the question carefully

>> No.10578325

>>10578317
I think that it’s saying that s and t are not coprime and they are not equal (at least, I’m assuming they can’t be equal, otherwise I think it would be too easy)

>> No.10578328

>>10578325
No, wait, it’s saying the only factor between the two is a single prime, which is not the same as not being coprime
Hmmm

>> No.10578329

>>10578153
Just think about the question for a bit. It's clearly a homework thread, as it's too easy for Putnam level. OP probably should be reported.

>> No.10578331 [DELETED] 

>>10578325
>I think that it’s saying that s and t are not coprime and they are not equal
It's saying gcd(s, t) is prime, which does imply s and t are coprime, but the converse isn't true. And of course they can be equal, don't make random assumptions

>> No.10578333

>>10578329
What's the solution?

>> No.10578338

>>10578325
>I think that it’s saying that s and t are not coprime and they are not equal
It's saying gcd(s, t) is prime, which does imply s and t are not coprime, but the converse isn't true. And of course they can be equal, don't make random assumptions

>> No.10578347

>>10578338
>And of course they can be equal, don't make random assumptions
I haven’t tried many high-level math problems, I didn’t know if it was obvious that they couldn’t be equal due to the notation or something

>> No.10578350

>>10578333
see>>10576711

>> No.10578352

>>10578322
You're right.
Somehow I missed the "for each integer n there is some s in S", and the complete lack of anything saying n is in any set at all.

>> No.10578356
File: 4 KB, 547x56, F2D907F3-F508-4A02-B222-FDAD2F36BDCE.gif [View same] [iqdb] [saucenao] [google]
10578356

>>10578329
Hmm

>> No.10578358

>>10578350
>or for n|s we have gcd(s,n) = n
That's not a problem, as long as there exists some s' in S such that gcd(s', n) = 1 or s', which he hasn't proven doesn't exist. He's only proven that for a specific n and s gcd(s, n) = n

>> No.10578359

>>10578356
This is the actual Putnam question from Harvard, if anyone still has doubts.

>> No.10578367

>>10578350
>>10578358
Just to clarify, his proof is wrong for the same reason why >>10578303 is wrong

>> No.10578371

>>10578356
What does “positive” mean in the context of complex numbers? Do both parts have to be positive, or only the real part?

>> No.10578379

>>10578358
Let S not contain primes. Then we have a prime n|s for some s in S, and the gcd conditions are not met. Assuming s and t are not unique (otherwise the statement is false), we are done.

>> No.10578390

>>10578379
Did you even read the post you're responding to?

>> No.10578393

>>10578390
no, I didn't have to because I knew it was wrong.

>> No.10578394 [DELETED] 

>>10578379
Why did you just post the same wrong proof again?
>Then we have a prime n|s for some s in S, and the gcd conditions are not met.
You have shown that for a specific n and s in S, gcd(s, n) does not equal 1 or s. What if for some other s' in S, gcd(s, n) does meet the gcd condition?

>> No.10578403

So wait, what even is the putnam question?

>> No.10578405

>>10578403
>>10578356

>> No.10578407

>>10578394
>it's a troll thread, not a homework thread
If some other s' meets the gcd condition, s' is prime.

>> No.10578410

>>10578379
Why did you just post the same wrong proof again?
>Then we have a prime n|s for some s in S, and the gcd conditions are not met.
You have shown that for a specific n and s in S, gcd(s, n) does not equal 1 or s. What if for some other s' in S, gcd(s', n) does meet the gcd condition? The requirement is not that all for integer n and s in S, gcd(s, n) = 1 or s. It's that for all n, there exists some s in S such that gcd(s, n) = 1 or s.

>> No.10578418

>>10578407
Why? You didn't explain that in your proof. You just said the gcd conditions are not met

>> No.10578421

>>10578418
figure it out, bub

>> No.10578426

>>10578421
Yeah I figured it out

>> No.10578430

>>10578426
good job

>> No.10578461
File: 67 KB, 800x610, wat.jpg [View same] [iqdb] [saucenao] [google]
10578461

What the fuck are you guys talking about, saying it's not a putnam problem?

It's from the 1999 exam, problem B-6:
https://kskedlaya.org/putnam-archive/1999.pdf

And here is the solution:
https://kskedlaya.org/putnam-archive/1999s.pdf

>> No.10578503

>>10576533
Strange question, I don't see where's the trick. First of all it's not stated whether it's possible for s=t or not, but since size of S is also undefined then S containing only one element is possible and s=t is necessary. Though I might be wrong. If s could be equal t then we have to proof that S contains at least one prime p, then gcd(p,p) is also prime. To do thant just use Sieve of Eratosthenes, since the set S is finite, it contains the biggest number s'. If s' is prime we're done, if not we eventually will find some prime number: condition gcd(s,n) = 1 or gcd(s,n) = s implies that if S contains some number divisible by 2, it also contains 2; if S contains some number divisible by 3, it also contains 3 and so on for every prime p=<s'.

>> No.10578518

>>10576533
so basically you can solve this by proving that if you have s,n such that gcd(s,n)=s, then for s there must exist s2 such that gcd(s2,s)=s2 and so on and so on
So each time you repeat that action Sn becomes a smaller chain of primes and in the end Sn must bea prime right?
that's my idea... Please let me now if I'm going the right way

>> No.10578521

>>10578518
Looks good I think.

>> No.10578528

>>10578461
I ain't clicking that link, nigga.

>> No.10578540

>>10578518
>if you have s,n such that gcd(s,n)=s, then for s there must exist s2 such that gcd(s2,s)=s2

I'm a bit confused by this.
How would that work for S={pq,qr,rp} where p,q,r are prime?

>> No.10578549

>>10578503
Incorrect.
S doesn't need to have any primes.
S={pq,qr,rp} is a counterexample.

>> No.10578567

>>10578350
>>10578379
Wrong. See >>10578549

>> No.10578575

It is trivial to see that the elements of S have to be products of primes to the firs tpower

>> No.10578611

>>10578540
that set doesn't satisfy the initial copnditions
since for pq there is no element in S such that gcd(s,pq)= s and there is no element in S such that gcd(s,pq)=1 as pq shares a factor greater than one for every other element

>> No.10578617

>>10578611
>there is no element in S such that gcd(s,pq)= s
There is, namely pq

>> No.10578631

>>10578575
mind explaining to a brainlet
I think I might have a solution but I have a question is S=(a,b) a valid set? with a,b being corprime, it's obviously not right?

>> No.10578633

>>10578617
well if you can take s=n the I think you have a counterexample

>> No.10578636

>>10578633
>>10578617
sorrry not a coutnerexample but you've basically proven that S cna have any intergers in it

>> No.10578638

>>10578633
Of course s can equal n. Where in the question does it suggest otherwise?

>> No.10578643

>>10578638
geez nigga let a brainlet be, I thought I had a solution but it only worked it s=/=n

>> No.10578647

>>10578636
>you've basically proven that S cna have any intergers in it
No? Take {4}, it does not satisfy the conditions.

>> No.10578650

>>10578643
>>10578638
besides if s=n is allowed then isn't {8} a valid set and a counterexample

>> No.10578656

>>10578631
Actually I don't even know if what I said is true

>> No.10578657

>>10578650
>isn't {8} a valid set
No, I choose n=2. Now show me an s in {8} such that gcd(2,s) = s or 1.

>> No.10578666

>>10578657
sorry I thought n had to belong to S
silly me

>> No.10578678

>>10578666
You and a bunch of others in this thread
I think it’s poorly worded

>> No.10578685

>>10578678
No it isn't. You guys just need to learn how to read problems

>> No.10578713

>>10578685
This thread.
https://www.youtube.com/watch?v=kTcRRaXV-fg

>> No.10578714

Daily Putnam Problem >>10578703

>> No.10578718

>>10578685
>for each integer n
Does that include negative integers? What about Gaussian integers? Why do you have to act like a tough guy over the Internet?

>> No.10578722

>>10578714
thank you based putnam poster

>> No.10578731

>>10578718
>negative integers
Yes, because they're integers
>Gaussian integers
No, because they're not integers

>> No.10578743

>>10578722
[math]
\color{red} \heartsuit
[/math]