0
$\begingroup$

If there is a finite set of $k$ integers how can I prove that there is a coprime for each number in the set?

That is pretty obvious but what is the formal way to prove this?

$\endgroup$
2
  • 1
    $\begingroup$ Apart from the word "set", how is this related to set theory? $\endgroup$ – Asaf Karagila Apr 1 '13 at 12:55
  • $\begingroup$ For every integer $n$, $1$ and $n$ are coprime. Restricting to a finite set of integers $n$ will not change that. Now did you want a coprime within the same set? Not true in general. $\endgroup$ – Julien Apr 1 '13 at 13:30
4
$\begingroup$

Take any prime number strictly greater than every element in the set. (Such prime does exist because the set is finite and there are infinitely many prime numbers).

$\endgroup$
6
$\begingroup$

Take as this number their product + 1.

$\endgroup$
0
$\begingroup$

You are asking to prove a false thing, since you are implicitely assuming $0 \not \in \mathcal{S}$, where $\mathcal{S}:=\{a_1,\ldots,a_k\}\subseteq \mathbb{Z}$ for some $k \in \mathbb{N} \setminus \{0\}$ is your fixed set. Indeed, $\text{gcd}(0,z)=z$ for all $z \in \mathbb{Z}\setminus \{0\}$, so that $0\not\in \mathcal{S}$ is a necessary condition. But it's also sufficient: define the radical $$\text{rad}\colon \mathbb{Z} \setminus \{0\} \to \mathbb{N}\colon z \mapsto \prod_{p \in \mathbb{P}:\text{ }p\mid z^2}{p},$$ and then the (positive squarefree) integer $$A:=\text{rad}\left(\prod_{1\le i\le k}{|a_i|}\right)=\text{lcm}\left(\text{rad}(|a_1|),\ldots,\text{rad}(|a_k|)\right).$$ It's clear that for all $z \in \mathbb{Z}$ we have $$\text{gcd}(z,A)=1\text{ iff }\text{gcd}(z,a_i)=1 \text{ for all }i=1,\ldots,k$$ Defin $\mathcal{Z}$ the set of such integers. It's clear that $|\mathcal{Z}|=\infty$, for example by Chinese remainder theorem, or for example taking a particular classes of integers, like $kA\pm 1$ for $k \in \mathbb{Z}$. It's even possible to give asymptotic cardinality for $\mathcal{Z}$, indeed $$|\mathcal{Z} \cap [-x,x]| \sim 2x\frac{\varphi(A)}{A}\text{ with }x\to +\infty.$$ It shows a bit stronger fact: If $\omega(\text{rad}\left(\prod_{s \in \mathcal{S}}{s}\right))$ is finite (allowing even a not finite set $\mathcal{S}$, then there exists positive constants $A,B$ such that $$Ax<|\mathcal{Z}\cap [-x,x]|<Bx$$ for all positive integers $x$.

A more interesting exercise can be the fact that $\omega(A) \to \infty$ implies $\frac{\varphi(A)}{A} \to 0$.

Edit: as usual $\varphi:\mathbb{N}\setminus \{0\} \to \mathbb{N}:n \mapsto |\{m \in \mathbb{N}\setminus \{0\}:\text{gcd}(m,n)=1\}|$ denotes the Euler indicator, and $\omega: \mathbb{N}\setminus \{0,1\} \to \mathbb{N}:n \mapsto |\{p \in \mathbb{P}:p\mid n\}|$ represents the number of prime divisors of a integer $n\ge 2$..

$\endgroup$
4
  • $\begingroup$ +1 It would be helpful to say what $\omega$ denotes, and to give the reader some references for the general results. Welcome to MSE. $\endgroup$ – Math Gems Apr 1 '13 at 14:59
  • $\begingroup$ If you say that, also $\varphi(\cdot)$ should be defined, although it's well known what it means :) Anyway no, there are no external reference, I make the proper edit, thanks for the comment! $\endgroup$ – Paolo Leonetti Apr 1 '13 at 16:58
  • $\begingroup$ The $\omega$ notation is much less widely used than the notation for Euler's totient. Keep in mind that our readers our diverse, so it is always helpful to explain any special notation. I presumed that you knew references for those results. $\endgroup$ – Math Gems Apr 1 '13 at 18:02
  • $\begingroup$ I wonder if $1$ is coprime to $0$. (Also $\gcd(0,z)=|z|$ for all $z \in \mathbb{Z} \setminus \{0\}$.) $\endgroup$ – Douglas S. Stones Apr 8 '13 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.