Let $n$ be a positive integer. Prove that there exists a finite sequence $S$ consisting of only zeros and ones, satisfying the following property: for any positive integer $d \geq 2$, when $S$ is interpreted in base $d$, the resulting number is non-zero and divisible by $n$. Remark: The sequence $S=s_ks_{k-1} \cdots s_1s_0$ interpreted in base $d$ is the number $\sum_{i=0}^{k}s_id^i$
Problem
Source: 2022 Switzerland IMO TST, Problem 1
Tags: number theory, Divisibility, number bases, Switzerland TST
CANBANKAN
01.08.2022 18:36
The problem essentially asks us to construct a polynomial $P$ with coefficients in $\{0,1\}$ such that $n\mid P(x)$ for all integers $x$.
I claim $P(x)=x^n (1+x^{\varphi(n)}+x^{2\varphi(n)} + \cdots + x^{(n-1)\varphi(n)})$ works.
Suppose $\nu_p(n)=k>0$. If $p\mid x$ then $p^k\mid P(x)$. Otherwise, by LTE, $\nu_p(1+x^{\varphi(n)}+\cdots+x^{(n-1)\varphi(n)}) = \nu_p(x^{n\varphi(n)}-1) - \nu_p(x^{\varphi(n)}-1) = \nu_p(n)=k$. The end.
NumberzAndStuff
31.10.2024 18:36
Consider some $x$ mod $n$ and its powers $x^1 \, x^2 \, x^3 \cdots$. Clearly These powers are eventually peridic modulo $n$, since there are finitely many residue classes mod $n$. Now take a common multiple of the period lengths in the appropriate spot. In other words for some $\lambda$: $x^{\lambda} \equiv x^{2\lambda} \equiv x^{3\lambda}$ and so on for any specific $x$. Now just select $n$ multiples of $\lambda$ as our indicies and we have: \[ \sum_{i=0} s_id^i \equiv n \cdot d^{\lambda} \equiv 0 \mod n \]
tyrantfire4
31.10.2024 18:39
Did you see the Marvel vs DC poll