Problem

Source: 2022 Switzerland IMO TST, Problem 1

Tags: number theory, Divisibility, number bases, Switzerland TST



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$