Processing math: 100%
 
+0  
 
-2
46
2
avatar+818 

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
avatar+121 
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,.

In our case, we want to find a positive integer m such that m7(modn) 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,.

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 m7(modn). 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 m7(modn) and gcd(m,n)=1.

 Aug 15, 2023
 #2
avatar+170 
0

Clearly this statement is false when 7|n.

 Aug 15, 2023

2 Online Users

avatar