Many Ones Deduction, Part I
Prerequisites: Modular arithmetic and geometric series.
In 2018, I participated in the Putnam Competition for the first and only time. In general, I think that math competitions tend to foster toxic and exclusive environments, of which I would like no part. But I still felt the impulse to participate in this toxicity and affirm myself through competition, so I signed up anyways, trying to tell myself that it was just for fun… Of course, that didn't really work, so I went scrounging for practice problems to "prepare" myself. I found that Alexander Givental had publicly posted homeworks for his Putnam Workshop, and a thread of related problems caught my eye. While the competition was ultimately as unrewarding as I should have expected, I did have fun thinking about these problems and I'd like to share those thoughts here.
For any positive integer $n$, we write $c_n$ for the natural number which consists of $n$ ones in its decimal expansion (e.g. $c_7=1111111$). We give three problems about the numbers $c_n$ below, each of which generalizes to any base $b$. The given solutions stick to base 10, but we will also state the more general hypotheses in terms of the base $b$. The interested reader is encouraged to tackle the general case. Please comment with any questions or observations regarding these problems and the subsequent discussion.
Problem 1: For integers $m,n>0$, show that $\gcd(c_m,c_n)=c_{\gcd(m,n)}$.
Solution: We will prove the desired formula by induction on $m+n$. The result is obvious when $m=n$, $m=1$ or $n=1$, so we assume without loss of generality that $m>n>1$. The greatest common divisor is a multiplicative function, meaning that $\gcd(ab,c)=\gcd(a,c)\cdot \gcd(b,c)$ when $\gcd(a,b)=1$. We also have $\gcd(x,y)=\gcd(x-y,y)$ for any positive integers $x$ and $y$. If $k=m-n>0$, then we have the equality $$c_m-c_n=\sum_{i=0}^{m-1}10^i-\sum_{j=0}^{n-1}10^j=\sum_{i=n}^{m-1}10^i=10^n\sum_{i=0}^{k-1}10^i=10^nc_k.$$ Note that $\gcd(10^i,c_j)=1$ for any positive integers $i$ and $j$. By the multiplicativity of $\gcd$, we have $$\gcd(c_m,c_n)=\gcd(c_m-c_n,c_n)=\gcd(10^n c_k,c_n)=\gcd(10^n,c_n)\cdot \gcd(c_k,c_n)=\gcd(c_k,c_n).$$ But $\gcd(k,n)=\gcd(m-n,n)=\gcd(m,n)$ and $k+n=m<m+n$. It follows by induction that $$\gcd(c_m,c_n)=\gcd(c_k,c_n)=c_{\gcd(k,n)}=c_{\gcd(m,n)}.$$
Problem 2: Let $a$ be a positive integer such that $\gcd(10,a)=1$ (or $\gcd (b,a)=1$ in the general case). Show that there exists a positive integer $n$ with $a\mid c_n$.
Solution: Since $\gcd(10,a)=1$, there exists a positive integer $k$ with $10^k\equiv 1(\text{mod }a)$. We will prove by induction that $c_{jk}\equiv jc_k(\text{mod }a)$ for all positive integers $j$. This is trivial for $j=1$. For greater $j$, we have $$c_{(j+1)k}=10^kc_{jk}+c_k\equiv c_{jk}+c_k\equiv jc_k+c_k=(j+1)c_k\, (\text{mod }a),$$ by induction. This proves that $c_{jk}\equiv jc_k(\text{mod }a)$ for all $j$. Setting $n=ak$, we have $c_n\equiv ac_k\equiv 0\,(\text{mod }a)$.
Problem 3: If $p$ is prime, show that $p\mid c_p$ if and only if $p=3$ (or $p\mid b-1$ in the general case).
Solution: Since $111=3\cdot 37$, we have $3\mid c_3$. Thus it suffices to assume that $p\neq 3$ and prove that $p\nmid c_p$. Since $p\neq 3$ and thus $p\nmid 9$, there exists an integer $k$ with $9k\equiv 1(\text{mod }p)$. Hence we have the following:
$$c_p=\sum_{i=0}^{p-1}10^i=\frac{10^p-1}{10-1}\equiv k(10^p-1)\,(\text{mod }p).$$ Since $k$ has a multiplicative inverse modulo $p$, we have $p\mid c_p\Longleftrightarrow p\mid 10^p-1$. Now assume for the sake of contradiction that $p\mid 10^p-1$. Fermat's little theorem implies that $10\equiv 10^p\equiv 1(\text{mod }p)$, which contradicts the assumption that $p\nmid 9=10-1$. Therefore, we have $p\nmid 10^p-1$ and thus $p\nmid c_p$, as originally desired.
Question: Problems 2 and 3 can be seen as facets of the following, more open-ended question, for which it is necessary to consider an arbitrary base $b$. We use the same symbol $c_n$, but it is now dependent on $b$.
Suppose that $a$ is a positive integer with $\gcd(b,a)=1$. Problem 2 shows that the sequence $(c_n\textbf{ mod } a)$ contains $0$. But $(c_n)$ is given by the recursive equation $c_{n+1}=bc_n+1$, and it follows that the sequence is periodic when considered modulo $a$. What is the period $P(a,b)$? This function satisfies the following:
In 2018, I participated in the Putnam Competition for the first and only time. In general, I think that math competitions tend to foster toxic and exclusive environments, of which I would like no part. But I still felt the impulse to participate in this toxicity and affirm myself through competition, so I signed up anyways, trying to tell myself that it was just for fun… Of course, that didn't really work, so I went scrounging for practice problems to "prepare" myself. I found that Alexander Givental had publicly posted homeworks for his Putnam Workshop, and a thread of related problems caught my eye. While the competition was ultimately as unrewarding as I should have expected, I did have fun thinking about these problems and I'd like to share those thoughts here.
For any positive integer $n$, we write $c_n$ for the natural number which consists of $n$ ones in its decimal expansion (e.g. $c_7=1111111$). We give three problems about the numbers $c_n$ below, each of which generalizes to any base $b$. The given solutions stick to base 10, but we will also state the more general hypotheses in terms of the base $b$. The interested reader is encouraged to tackle the general case. Please comment with any questions or observations regarding these problems and the subsequent discussion.
Problem 1: For integers $m,n>0$, show that $\gcd(c_m,c_n)=c_{\gcd(m,n)}$.
Solution: We will prove the desired formula by induction on $m+n$. The result is obvious when $m=n$, $m=1$ or $n=1$, so we assume without loss of generality that $m>n>1$. The greatest common divisor is a multiplicative function, meaning that $\gcd(ab,c)=\gcd(a,c)\cdot \gcd(b,c)$ when $\gcd(a,b)=1$. We also have $\gcd(x,y)=\gcd(x-y,y)$ for any positive integers $x$ and $y$. If $k=m-n>0$, then we have the equality $$c_m-c_n=\sum_{i=0}^{m-1}10^i-\sum_{j=0}^{n-1}10^j=\sum_{i=n}^{m-1}10^i=10^n\sum_{i=0}^{k-1}10^i=10^nc_k.$$ Note that $\gcd(10^i,c_j)=1$ for any positive integers $i$ and $j$. By the multiplicativity of $\gcd$, we have $$\gcd(c_m,c_n)=\gcd(c_m-c_n,c_n)=\gcd(10^n c_k,c_n)=\gcd(10^n,c_n)\cdot \gcd(c_k,c_n)=\gcd(c_k,c_n).$$ But $\gcd(k,n)=\gcd(m-n,n)=\gcd(m,n)$ and $k+n=m<m+n$. It follows by induction that $$\gcd(c_m,c_n)=\gcd(c_k,c_n)=c_{\gcd(k,n)}=c_{\gcd(m,n)}.$$
Problem 2: Let $a$ be a positive integer such that $\gcd(10,a)=1$ (or $\gcd (b,a)=1$ in the general case). Show that there exists a positive integer $n$ with $a\mid c_n$.
Solution: Since $\gcd(10,a)=1$, there exists a positive integer $k$ with $10^k\equiv 1(\text{mod }a)$. We will prove by induction that $c_{jk}\equiv jc_k(\text{mod }a)$ for all positive integers $j$. This is trivial for $j=1$. For greater $j$, we have $$c_{(j+1)k}=10^kc_{jk}+c_k\equiv c_{jk}+c_k\equiv jc_k+c_k=(j+1)c_k\, (\text{mod }a),$$ by induction. This proves that $c_{jk}\equiv jc_k(\text{mod }a)$ for all $j$. Setting $n=ak$, we have $c_n\equiv ac_k\equiv 0\,(\text{mod }a)$.
Problem 3: If $p$ is prime, show that $p\mid c_p$ if and only if $p=3$ (or $p\mid b-1$ in the general case).
Solution: Since $111=3\cdot 37$, we have $3\mid c_3$. Thus it suffices to assume that $p\neq 3$ and prove that $p\nmid c_p$. Since $p\neq 3$ and thus $p\nmid 9$, there exists an integer $k$ with $9k\equiv 1(\text{mod }p)$. Hence we have the following:
$$c_p=\sum_{i=0}^{p-1}10^i=\frac{10^p-1}{10-1}\equiv k(10^p-1)\,(\text{mod }p).$$ Since $k$ has a multiplicative inverse modulo $p$, we have $p\mid c_p\Longleftrightarrow p\mid 10^p-1$. Now assume for the sake of contradiction that $p\mid 10^p-1$. Fermat's little theorem implies that $10\equiv 10^p\equiv 1(\text{mod }p)$, which contradicts the assumption that $p\nmid 9=10-1$. Therefore, we have $p\nmid 10^p-1$ and thus $p\nmid c_p$, as originally desired.
Question: Problems 2 and 3 can be seen as facets of the following, more open-ended question, for which it is necessary to consider an arbitrary base $b$. We use the same symbol $c_n$, but it is now dependent on $b$.
Suppose that $a$ is a positive integer with $\gcd(b,a)=1$. Problem 2 shows that the sequence $(c_n\textbf{ mod } a)$ contains $0$. But $(c_n)$ is given by the recursive equation $c_{n+1}=bc_n+1$, and it follows that the sequence is periodic when considered modulo $a$. What is the period $P(a,b)$? This function satisfies the following:
- $P(a,b)$ is the smallest positive integer $n$ such that $a\mid c_n$.
- For any positive integer $n$, we have $a\mid c_n\Longleftrightarrow P(a,b)\mid n$.
- $P(a,b)$ is the number of residues mod $a$ occuring in the sequence $(c_n)$.
- $P(a,b)$ depends only on $a$ and $b\textbf{ mod }a$, not on the specific value of $b$.
- $1\leq P(a,b)\leq a$ for all $a$ and $b$.
- If $b\equiv 1(\text{mod }a)$, then $P(a,b)=a$.
Does this pattern continue? If so, why? What is special about the value it seems to be converging to???
Comments
Post a Comment