+0

# need help

-1
7
2

Can anyone give a hint here?

Given a positive integer $n,$ prove that there exists a positive integer $m > 1000$ such that $m \equiv 7 \pmod{n}$ and $\gcd(m,n) = 1.$

Aug 15, 2023

#1
0

To prove this statement, we'll use the Dirichlet's theorem on arithmetic progressions. Dirichlet's theorem states that for any two coprime positive integers $$a$$ and $$d$$, there are infinitely many primes in the arithmetic progression $$a, a + d, a + 2d, \ldots$$.

In our case, we want to find a positive integer $$m$$ such that $$m \equiv 7 \pmod{n}$$ and $$\gcd(m,n) = 1$$. Let $$d = n$$ and $$a = 7$$. Since $$\gcd(7, n) = 1$$ (as $$n$$ is a positive integer), Dirichlet's theorem guarantees that there are infinitely many primes in the arithmetic progression $$7, 7 + n, 7 + 2n, \ldots$$.

Let's consider a prime number in this progression that is greater than 1000. Since $$n$$ is fixed, as we go further along the progression, the numbers will become larger, and eventually, we will find a prime $$m > 1000$$ that satisfies $$m \equiv 7 \pmod{n}$$. Moreover, since the prime is greater than 1000 and $$n$$ is a positive integer, it's guaranteed that $$\gcd(m, n) = 1$$ because a prime greater than 1000 cannot have any factors in common with $$n$$.

Therefore, we have shown that for any positive integer $$n$$, there exists a positive integer $$m > 1000$$ such that $$m \equiv 7 \pmod{n}$$ and $$\gcd(m,n) = 1$$.

Aug 15, 2023
#2
+1

Clearly this statement is false when $$7\vert n$$.

Aug 15, 2023