Saudi Arabia booklet 2024

We claim that the only integers that work are prime powers $p^k$ in which $p\equiv 5$ or $7$ modulo $8$. Let define $\omega ,\Omega$ as function from the set of odd integers to $\{0;1\}$ by $$\omega (n)=\{\begin{array}{ll}0& \text{if }n\equiv 1,3(\mathrm{mod}8)\\ 1& \text{if }n\equiv 5,7(\mathrm{mod}8)\end{array}$$ and $$\Omega (n)\equiv |\{k\mid 0<k<n/4,\gcd (k,n)=1\}|(\mathrm{mod}2).$$ Then we want to find $n$ such that $\Omega (n)=1$. It is easy to verify $$\omega (ab)\equiv \omega (a)+\omega (b)(\mathrm{mod}2)(†)$$ Let $n=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}$ which $p_1,p_2,\dots ,p_k$ are distinct primes and $a_1,a_2,\dots ,a_k$ are integers. Note that $n=1$ does not work so consider $k\ge 1$.

Lemma: $\Omega (n)\equiv \omega (n)+{\sum }_{1\le i\le k}\omega \left(\frac{n}{p_i}\right)+{\sum }_{1\le i<j\le k}\omega \left(\frac{n}{p_i{p}_j}\right)+\cdots +\omega \left(\frac{n}{p_1{p}_2\dots p_k}\right)(\mathrm{mod}2)$.

Proof: the idea to proof this lemma is similar to prove the Euler totient function. It is easy to check that $\omega (n)$ is indeed the parity of $|\{k\mid 0<k<n/4\}|=\lfloor \frac{n}{4}\rfloor$. To remove numbers divisible by some $p$, one can subtract from above the value $$|\{pk\mid 0<k<n/(4p)\}|=|\{k\mid 0<k<(n/p)/4\}|=\omega \left(\frac{n}{p}\right).$$ But that removes numbers divisible by $pq$ (for $p\ne q$) twice so we will add $\omega (pq)$ then continue as the principle of inclusion and exclusion, we add until $\omega \left(\frac{n}{p_1{p}_2\dots p_k}\right)$. Note that the formula should be added and subtracted alternatively but since we consider modulo $2$ so all of the signs can be consider as plus. Back to the original problem, by applying the lemma and $(†)$, one can get $$\begin{array}{rl}& \Omega (n)+\sum _{1\le i\le k}\omega (p_i)+\sum _{1\le i<j\le k}\omega (p_i{p}_j)+\cdots +\omega (p_1{p}_2\dots p_k)\\ & \equiv \omega (n)+\left(\sum _{1\le i\le k}\omega \left(\frac{n}{p_i}\right)+\sum _{1\le i\le k}\omega (p_i)\right)+\cdots +\left(\omega \left(\frac{n}{p_1{p}_2\dots p_k}\right)+\omega (p_1{p}_2\dots p_k)\right)\\ & \equiv \left(\genfrac{}{}{0ex}{}{k}{0}\right)\omega (n)+\left(\genfrac{}{}{0ex}{}{k}{1}\right)\omega (n)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)\omega (n)+\cdots +\left(\genfrac{}{}{0ex}{}{k}{k}\right)\omega (n)\\ & \equiv 2^k\omega (n)\equiv 0(\mathrm{mod}2).\end{array}$$ From this, one can conclude that $$\begin{array}{rl}\Omega (n)& \equiv \omega (1)+\sum _{1\le i\le k}\omega (p_i)+\sum _{1\le i<j\le k}\omega (p_i{p}_j)+\cdots +\omega (p_1{p}_2\dots p_k)\\ & =\sum _{i=1}^k\left(\left(\genfrac{}{}{0ex}{}{k-1}{0}\right)+\left(\genfrac{}{}{0ex}{}{k-1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{k-1}{k-2}\right)\right)\omega (p_i)\\ & =2^{k-1}\sum _{i=1}^n\omega (p_i)\\ & =2^{k-1}\omega (p_1{p}_2\dots p_k)(\mathrm{mod}2).\end{array}$$ Thus if $k\ge 2$ then $\Omega (n)=0$ and if $k=1$, then $n=p^k$, in this case we can check that $\Omega (n)=\omega (p)=1$ if and only if $p\equiv 5$ or $7$ modulo $8$. $\square$