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.