Let $ \mathbb{P}= \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $ \mathcal{Q}= \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$. Then letting $ k = q \cdot \prod_{p \in \mathcal{Q}}p$ yields $ \gcd(ak+b, n) = 1$, for each $ q \in \mathbb{P}$ such that $ q > n$.

Consequence There exist infinite prime number.

s.tringali wrote: Let $ \mathbb{P} = \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $ \mathcal{Q} = \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$. Then letting $ k = q \cdot \prod_{p \in \mathcal{Q}}p$ yields $ \gcd(ak + b, n) = 1$, for each $ q \in \mathbb{P}$ such that $ q > n$. I don't understand. What if $ \mathcal Q$ is empty, for example if $ n|b$? What if $ \mathcal Q$ is infinite? Then $ \prod_{p \in \mathcal{Q}}p$ is not a number.

I am also. Here is my solution: Enough to prove exist because if $ \gcd(ak + b,n) = 1$ then $ \gcd(a(k + nt) + b,m) = 1$ Now we prove this : $ n = \prod_{i = 1}^rp_i^{a_i}$ where $ a_i > 0$ Now place each of them to one of set. $ A = \{p\in P: p|\gcd(b,n)\}$ $ B = \{p\in P: p|n,\gcd(p,b) = 1\}$ Because $ \gcd(a,b) = 1$ so $ p\not|a,\forall p\in A$ Now we consider the system of congruent: $ k\equiv 1 (\mod\prod_{p\in A}p)$ $ k\equiv 0 (\mod \prod _{p\in B})$ This equation has solution (Chinese remainder theorem). Easy to check that $ \gcd(ak + b,n) = 1$

It seems like this should have a simple arithmetic solution, since it can be rephrased as: Let a, b, n, x and y be integers with $ ax+by=1$ and $ n\ne 0$. Show that there exists integers z, k and w such that $ z(ak+b)+wn=1$. The closest I could come does use the following lemma. Lemma: For every pair of positive integers $ n, b$, there exists a representation $ n=n_1n_2$ where $ n_2$ is coprime to $ b$ and $ n_1$ is a factor of a power of $ b$. Proof: Let $ t_0=n$, and define sequences $ t_i, u_i$ by $ u_i=\gcd(t_i,b)$, $ t_{i+1}=\frac{t_i}{u_i}$. Since $ u_i\ge 1$, $ t_{i+1}\le t_i$ and the positive integer sequence eventually becomes constant. Suppose $ t_k=t_{k+1}$. Then set $ n_2=t_k$ and $ n_1=u_1u_2\ldots u_{k-1}$. Clearly $ n=n_2$, $ t_k$ is coprime to $ b$, and since each $ u_i$ is a factor of $ b$, $ n_1$ is a factor of $ b^{k-1}$. QED It is not hard to see that this representation is unique, but we won't use that. Given our n, a, b from the problem, we know that $ \gcd(a,b)=1$, which means that $ \gcd(b,a+b)=1$. From the above lemma, we can write $ n=n_1n_2$ where $ n_2$ is coprime to $ b$ and $ n_1$ is a factor of a power of $ b$. Since $ n_1$ is a factor of a power of $ b$, it is coprime to all things coprime to $ b$, in particular to $ n_2$ and to $ a+b$. Thus we have the existence of integers $ x_i, y_i$ such that $ x_1n_1+y_1n_2=1$, $ x_2n_1+y_2(a+b)=1$ and $ x_3n_2+y_3b=1$. Then: $ y_3(b+y_1n_2a)=y_3b+y_3y_1n_2a=1-x_3n_2+y_3y_1n_2a=1+(y_3y_1a-x_3)n_2$, so $ b+y_1n_2a$ is coprime to $ n_2$. Similarly, $ y_2(b+y_1n_2a)=y_2(b+(1-x_1n_1)a)=y_2(b+a)-y_2x_1n_1a=1-x_2n_1-y_2x_1n_1a=1-(x_2+y_2x_1a)n_1$, so $ b+y_1n_2a$ is coprime to $ n_1$. Thus $ b+y_1n_2a$ is coprime to $ n_1n_2=n$. Luke See my puzzle blog at http://bozzball.blogspot.com/[/b]