Does there exist such infinite set of positive integers $S$ that satisfies the condition below? *for all $a,b$ in $S$, there exists an odd integer $k$ that $a$ divides $b^k+1$.
Problem
Source: 2021 Korea Winter Program Practice Test
Tags: number theory, IMO Shortlist
09.02.2021 07:07
Construct $S $ from $pq $ where $p $ and $q $ are the prime numbers $=3 (4). $ Let $p_1 <q_1 < p_2 < q_2\hdots$ be a sequence of prime numbers. Note that $p_1=3,q_1=7$ and $q_{n+1},p_{n+1} $ are chosen hence $p_{n+1} $ is a square $\pmod{p_i} $ and a square $\pmod{q_i}\,\forall\,i\le n $ Applying quadratic reciprocity note that $p_i $ is a square $\pmod{p_j}$ and a nonsquare $\pmod {q_j}\, i>j. $ $q_i $ is a nonsquare $\pmod{p_j} $ and a square $\pmod{q_j} \, j>i$ $\pmod_{q_j} $ is a square $\pmod {p_j}$ and a nonsquare $\pmod{q_j}\,j>i. $ If $z $ is a nonsquare modulo a prime $p=3(4). $ $x^{\frac {(p-1)}{2}}+1$ is a multiple of $p. $ From the above results note that, $p_i q_i $ is a nonsquare both $\pmod{p_j}$ and $\pmod{q_j} $ for $i\ne j $ By choosing $(p_j-1)\cdot\frac {(q_j-1)}{4} $ as exponent we obtain the result $(S=\{p_i q_i\}) $
17.07.2024 21:55
Consider $p,q$ be odd primes. Then $q$ is a quadratic nonresidue $\mathrm{mod\,p}$ iff $q^{\frac{(p-1)}{2}}\equiv \,-1(p)$. If at least one of $p,q$ is $\mathrm{1\, (mod\, 4)}$ then quadratic reciprocity implies that $p$ is a square $\mathrm{mod\, q}$ iff $q$ is a square $\mathrm{mod\, p}.$ Let $S$ be a finite set of primes all $\mathrm{1\,mod\, 4}$ such that for every distinct $p,q\in S$ we have $$\left(\frac{p}{q}\right)=-1$$For each $p\in S$ choose a class $a_p\mathrm{mod\, p}$ such that $\left(\frac{a_p}{p}\right)=-1.$ Let $M=4\prod_{p\in S}p$ then by chinese remainder theorem there $a\,\mathrm{mod}\, M$ such that $a\equiv a_p\, (p)\, \forall p\in S \, , a\equiv1\,(4).$ By choice of the $a_p$ note that $a$ is not divisible by $p$ and also odd $, (a,M)=1.$ Applying Dirichlet's theorem on primes in arithmetic progressions that is a prime $q$ such that $q\equiv a\,(M).$ Then $q$ is a quadratic nonresidue $\mathrm {mod\,4}$ also every $p\in S$ is a nonresidue $\mathrm{mod\, q}.$ so we can add $q$ to $S$ and continue recursively