I'm born for regret minimization

No content.

Statement as follows:

\forall g, k \in Z w i t h g c d (g, k) = 1, i t h o l d s \forall t \in Z \exists a \in Z s u c h t h a t g c d (t, g + a k) = 1.

Proof:

Fix such $g, k \in Z$ and arbitrary $t \in Z$ . Factorize $t = \prod_{i = 1}^{n} p_{i}^{e_{i}}$ .

Consider $p_{i}^{e_{i}}$ for any $1 \leq i \leq n$ :

If $p_{i} ∣ k$ and $p_{i} ∤ g$ , then $g c d (p_{i}^{e_{i}}, g + a k) = 1$ for any $a \in Z$ .

If $p_{i} ∤ k$ , then $g c d (p_{i}^{e_{i}}, k) = 1$ . Proceed as follows:

Let set $T = {a \in N \cup {0} : a < p_{i}^{e_{i}}}$ and $S = {g + a k : a \in T}$ .

Let function $f : S \to T$ by $g + a k \mapsto g + a k \mod p_{i}^{e_{i}}$ .

If $g + a_{1} k \equiv g + a_{2} k \mod p_{i}^{e_{i}}$ (and we know $g c d (p_{i}^{e_{i}}, k) = 1$ ), then $p_{i}^{e_{i}} ∣ (a_{2} - a_{1})$ .

This then implies $a_{2} = a_{1}$ by definition of $T$ , so $f$ is injective.

By injectivity, we have $T = f (S)$ , which then implies $\exists a_{i} \in T$ such that $g + a_{i} k \equiv 1 \mod p_{i}^{e_{i}}$ and so $g c d (g + a_{i} k, p_{i}^{e_{i}}) = 1$ .

Finally, by Chinese Reminder Theorem (which I completely forget now), we get $\exists a \in Z$ such that $a \equiv a_{i} \mod p_{i}^{e_{i}}$ for all $i$ where $p_{i} ∤ k$ . And for this $a$ , one can check $g c d (g + a k, t) = 1$ .