Let $P$ be the set of all prime numbers. Let $A$ be some subset of $P$ that has at least two elements. Let's say that for every positive integer $n$ the following statement holds: If we take $n$ different elements $p_1,p_2...p_n \in A$, every prime number that divides $p_1 p_2 \cdots p_n-1$ is also an element of $A$. Prove, that $A$ contains all prime numbers.
Problem
Source: 2019 Slovenia 1st TST Problem 4
Tags: TST, number theory
MessingWithMath
19.02.2019 02:14
Hoepfully not fake solve: Obviously, there are infinite numbers in $A$. (we may establish contradiction otherwise by taking $n=|A|$). By contradiction, assume a prime $q$ isn't in $A$. Thus, there exists a value $a$ such that there are infinite distinct values in $A$ that are $a \pmod{q}$ by pigeonhole. Note how $a\neq 0$ since all values are prime. By Fermat's little theorem, we may take $q-1$ of these numbers and notice that $p_1p_2\cdots p_{q-1}-1\equiv 0 \pmod{q}$. thus, we arrive at a contradiction as $q$ must exist in the set. Thus, all prime numbers are in $A$. ALSO WHERE IS QUESTION 3?????
pj294
19.02.2019 02:20
MessingWithMath wrote: ALSO WHERE IS QUESTION 3????? Sadly I'm limited to 3 posts per day as I am a new member, so problems 3 and 5 are coming tomorrow.
MessingWithMath
19.02.2019 02:20
Rip okay. Also did you take the TST? did you full solve?
pj294
19.02.2019 02:28
MessingWithMath wrote: Rip okay. Also did you take the TST? did you full solve? I did, but I didn't do very well. I'm new to the whole thing.
MessingWithMath
19.02.2019 02:32
Lol, if you don't mind me asking, how did you do? This is also my first year doing olympiads legit. I qualified for and failed all the major ones last year (APMO, CMO, USAMO)
pj294
19.02.2019 02:39
MessingWithMath wrote: Lol, if you don't mind me asking, how did you do? This is also my first year doing olympiads legit. I qualified for and failed all the major ones last year (APMO, CMO, USAMO) I solved P1 and got some partial marks on P4. I was still ˝scared˝ of inequalities so I didn't even attempt the easy P2. In Slovenia the TSTs are somewhat independant of other competitions and anyone can attend the first two, and top 25 get selected for the final third one. I only found out about the IMO and other olympiads about 5 months ago .
MessingWithMath
19.02.2019 03:02
Oh rip. That also explains why you might have been such a new member to AoPs. TBH I only got on aops recently too!
v_Enhance
19.02.2019 07:36
Also Romania TST 2003 (similar to USA TSTST 2015).