Accessibility and divisibility

Section 48.5 Accessibility and divisibility

Theorem 48.5.1.

For \(c\in\mathbb{Z}^+\backslash\{1\}\) the set \(B=\{c^i(c^j-1):i,j\in \mathbb{Z}^+\}\) is accessible.

Proof.

Let \(\chi:\mathbb{Z}^+\rightarrow A\) be a colouring of the natural numbers with \(|A|\in\mathbb{Z}^+\text{,}\) and have the set \(X=\{x+c^i:i\in \mathbb{Z}^+\}\) for some \(x\in\mathbb{Z}^+\text{.}\) The difference between any 2 distinct elements of \(X\) is \(x+c^i-(x+c^j)\) with \(i\gt j\text{.}\) Notice \(x+c^i-(x+c^j)=c^j(c^{i-j}-1)\in B\text{.}\) Let the colouring \(\phi(y)=\chi(x+c^y)\) applying van der Waerden theorem on \(\phi\) we know there exists arbitrarily long monochromatic arithmetic progressions in \(\phi\text{,}\) so by construction of \(\phi\) there exists arbitrarily long monochromatic \(B\)–diffsequences in \(\chi\text{.}\)

Theorem 48.5.2.

Let the set \(A\) be accessible, then for all \(p\in\mathbb{Z}^+\) there exists an \(a\in A\) such that \(p|a\text{.}\)

Proof.

Assume for a contradiction that there exists a \(p\) such that for all elements \(a\in A\text{,}\) \(p\nmid a\text{.}\) Let the colouring \(\chi\) be defined as \(\chi:\mathbb{Z}^+\rightarrow \{0,1,2,\ldots,p-1\}\) and \(\chi(x)=x\bmod{p}\text{.}\) Then if \(x\) and \(a\) are integers with \(a\in A\) the following holds.

\begin{equation*} \chi(x)=x\bmod{p}\neq (x+a)\bmod{p}=\chi(x+a)\text{.} \end{equation*}

Thus \(A\) is not accessible, which is a contradiction.

From Theorem 48.5.1 and Theorem 48.5.2, we can prove a weaker version of Euler's theorem which states that \(c^{\Phi(p)}\equiv1\pmod{p}\text{.}\)

Theorem 48.5.3.

For all \(p\) co–prime to \(c\text{,}\) there exists an \(i\) such that \(p\) divides \(c^{i}-1\text{.}\)

Proof.

Let \(c\) be an integer and \(c\gt 1\) appealing to Theorem 48.5.1 yields, \(B=\{c^i(c^j-1):i,j\in \mathbb{Z}^+\}\) is accessible. So applying Theorem 48.5.2 for all \(p\) with \(\text{gcd }(p,c)=1\text{,}\) there exists \(b\in B\) such that \(p|b\)

\begin{equation*} p|b \Leftarrow p|c^j(c^i-1) \Leftarrow p|(c^i-1)\text{.} \end{equation*}

So \(c^i\equiv1\pmod{p}\) for some \(i\in\mathbb{Z}^+\text{.}\)

This is one of my favourite proofs in [48.7.2] and inspiration for the set \(B\text{.}\)

Theorem 48.5.4.

Let \(S=\{b_i\}_{i=1}^\infty\) and \(\{b\}\) to satisfy the recurrence relationship \(b_n=cb_{n-1}+b_{n-2}\) with \(c\text{,}\) \(b_1\text{,}\) \(b_2\in\mathbb{Z}^+\text{.}\) Then \(S\cup cS\) is \(2\)–accessible.

Proof.

By contradiction, assume that \(S\cup cS\) is not \(2\)–accessible, then there exists a largest monochromatic \(S\cup cS\)–diffsequence called \(\{x_i\}_{i=1}^n\) say it is red. Then the set \(X=\{x_n+b_i:i\in\mathbb{Z}^+\}\) is blue, but \((x_n+b_{n+2})-(x_n+b_{n})=cb_{n+1}\in cS\) , so \(X\) is an arbitrarily large \(cS\)–diffsequence.