Variety of proofs of a simple proposition in arithmetic

Question

I have a couple of simple proofs of a simple proposition and I'm curious to see the variety of different approaches others would take to prove the same thing.

Definition: The dilation of a sequence $a_1, a_2, a_3,\ldots$ by a factor $n$ is the sequence $b_1,b_2,b_3,\ldots$ for which $$ \begin{cases} b_{kn} = a_k & \text{for } k=1,2,3,\ldots, \\ b_j = 0 & \text{if $j$ is not a multiple of $n$.} \end{cases} $$ Thus the dilation of $a_1,a_2,a_3,\ldots$ by a factor of $3$ is $$ 0,\ 0,\ a_1,\ 0,\ 0,\ a_2,\ 0,\ 0,\ a_3,\ 0,\ 0,\ a_4,\ \ldots $$ (This is not standard terminology as far as I know, so tell me if there's some standard name for this.)

Now let $\{a_k\}_{k=1}^\infty$ consist of an infinite sequence of repetitions of $1,0,0,0,1,0$ (a $\text{“}1\text{''}$ in the $1$st and $5$th positions and $\text{“}0\text{''s}$ elsewhere). In other words $a_k$ is just the indicator that $k$ is coprime to $6$.

Now start by letting $c$ be an infinite sequence of $0$s and proceed as follows:

1. Let $n$ be the smallest index for which $c_n=0$ (thus initially $n=1$);

2. Let the new value of $c$ be $(c + \text{the dilation of } a \text{ by } n)$ (where the occurrence of $c$ inside the round brackets is the value of $c$ we had at the end of step $1$.);

3. Go back to step $1$.

This goes on forever.

Proposition: This process converges to an infinite sequence of $1$s. (Thus, we never add $1$ to any position that was not $0$.)

As I said, I have a couple of simple proofs and I am curious to see the variety of different approaches others would take to prove the same thing.

Answer 1

Let $A$ be the set of numbers whose prime factors are in $\{2;3\}$ and $B$ be the set of numbers whose prime factors are not in $\{2;3\}$.

The fundamental theorem of arithmetic implies that (as multiplicative monoids) $\Bbb N = A \times B = \bigcup_{a \in A} aB$ and so $\Bbb N$ can be partitioned into dilations of $B$ (or into dilations of $A$ too but that's not the point here)

So we need to prove that with your procedure we obtain exactly those dilations, in the same order : that $a \in A$ if and only if $a$ is not in $a'B$ for some $a' < a$ but this is easy :

if $a \in A$ then $a$ is in the $aB$ piece and not any other piece.
If $a$ is not of the form $a'b$ with $b>1$ then since it also can't be $a'.b$ for $a'>a$, its decomposition has to be $a=a.1$ and so $a \in A$.

---

Interestingly, if $\Bbb N = A \times B$ for some submonoids $A$ and $B$ then this shows that $B$ is completely determined by $A$ (and vice-versa)

Answer 2

Let's see. The dilation of $a_n$ with a factor $k$ (we'll write $d(a_n,k,i)$ for this, where $i$ is the index) is the following: \begin{equation} d(a_n,k,i)= \begin{cases} 1 & \text{if } i=6kN\pm k\text{ for some }N\in\mathbb{Z}\\ 0 & \text{otherwise} \end{cases} \end{equation} Now we pick any $x\in\mathbb{N}$ and we look at for what $k$ we have $d(a_n,k,x)=1$. We see that $x=6kN\pm k$ for some $N\in\mathbb{Z}$, so $k\mid x$, and that $\frac xk\equiv \pm 1\mod 6$. For a number to be $\pm1\mod6$, it needs to be composed of primes $\pm1\mod 6$ only - that is, not $2$ or $3$. So we know that $k$ must have all the factors $2$ and $3$ that $x$ has, and $k$ may also have some additional factors $\pm1\mod6$ that $x$ has.

---

So we found a bunch of $k$'s that would have $d(a_n,k,x)=1$. But we have to prove that there's only one! Well, in the steps we did to get $c$, we only deligated $a_n$ by a factor $n$ if $n$ was the smallest number with $c_n=0$. We'll now prove that those $n$ are always of the form $2^a3^b$, and that all numbers of that form will be reached by $n$. We split this up into two cases.

Lemma. A number $n$ that once will be the smallest number with $c_n=0$ cannot be divisile by a number $\pm1\mod6$.

Proof. Let's assume $n$ has a divisor $\pm1\mod6$, let's call the largest such divisor $s$. But then $d(a_n,\frac ns,n)=0$, otherwise $c_n=1$. So $n\neq 6\frac nsN\pm \frac ns$ for all $N\in\mathbb{Z}$, but clearly, an $N_0$ such that $s=6N_0\pm 1$ exists (by assumption), so that $n=6\frac nsN_0\pm \frac ns$, which is a contradiction. Thus, the lemma must be true.

Lemma. A number of the form $n=2^a3^b$ will once be the smallest number such that $c_n=0$

Proof. Let's assume the lemma is false. Then we have a number $x=2^a3^b$ such that $d(a_n,y,x)=1$ for $x>y$. This means that $x=2^a3^b=6yN\pm y$ for some $N\in\mathbb{Z}$. But this means that $6N\pm1\mid 2^a3^b$, but this is impossible. Thus, the lemma must be true.

---

Thus, of all those $k$ that we found that have $d(a_n,k,x)=1$, only one will actually be reached as "smallest $k$ such that $c_k=0$", and that is the one with only factors $2$ and $3$ (and no factors $\pm1\mod 6$, thus, we see that, when taking the limit to an infinite amount of steps, that $c_x=1$. Since we did no assumptions for $x$, we have $c_x=1$ for all $x\in\mathbb{N}$. This completes the proof.

Answer 3

Alright, here's one way that I know of.

Suppose $N$ is an infinitely large integer (oh $\ldots$ um $\ldots$ TRIGGER WARNING: If you suffer pain and distress as a result of reading something whose rigorous definition has not been stated and might be problematic, then don't read the foregoing phrase) whose prime factorization contains infinitely many $2$s and infinitely many $3$s and nothing else. Look at the sequence $$ \frac 1 N, \frac 2 N, \frac 3 N,\ \ldots,\ \frac{N-3} N, \frac{N-2} N, \frac{N-1} N. \tag a $$ The first time one comes to step 2. in the algorithm, one adds $1$ in every position in $(\mathbf a)$ in which the fraction is in lowest terms.

The second time one comes to step 2., one adds a $1$ in every position in which one reduces the fraction to lowest terms only by dividing the numerator and denominator by $2$ (not including those cases in which division by $2$ reduces the fraction incompletely).

The third time one comes to step 2., one adds a $1$ in every position in which one reduces the fraction to lowest terms only by dividing the numerator and denominator by $3$ (not including those cases in which division by $3$ reduces the fraction incompletely).

The fourth time one comes to step 2., one adds a $1$ in every position in which one reduces the fraction to lowest terms only by dividing the numerator and denominator by $4$ (not including those cases in which division by $4$ reduces the fraction incompletely).

The fifth time one comes to step 2., one adds a $1$ in every position in which one reduces the fraction to lowest terms only by dividing the numerator and denominator by $6$ (not including those cases in which division by $6$ reduces the fraction incompletely).

and so on. One reduces by dividing by $2$, or $3$, or $4$, or $6$, or $8$, or $9$, or $12$, etc. This sequence contains all integers that have no prime factors except $2$ and $3$. This process will never reduce a fraction that's already reduced, so it never adds a $1$ to a position more than once.

\begin{align} & \frac{2520}{2\times2\times2\times\cdots \times 3\times3\times3\times\cdots} \\[10pt] = {} & \frac{\overbrace{2\times2\times2}\times\overbrace{3\times3}\times35}{2\times2\times2\times\cdots \times 3\times3\times3\times\cdots} \\[10pt] = {} & \frac{35}{\not2\times\not2\times\not2\times2\times2\times\cdots \times \not3\times\not3\times3\times3\times\cdots} \end{align} (It is not hard to rephrase all this in a way that doesn't mention an infinitely large integer.)

In a comment above I asked "How would you write this same argument in a way intended to make it comprehensible to secondary-school pupils while still keeping it simple?". This is how I would do that. So a question remains: Are there other ways, in some essential way different?