Number Theory Linear Diophantine Equations

Question

Let $n$ be a positive integer. Prove that there exists a positive integer $m > 1000$ with the following two properties: $m$'s last 3 digits are 007, and $m$ is relatively prime to $n$.

Can somebody provide me with a solution?

I have this so far: We know that having the last three digits of $m$ be $007$ means $m \equiv 7 \mod 1000.$ When $n$ has no factors of $2$ or $5,$ we can make congruences $m \equiv 1\mod p$ where $p$ is a prime that divides $n$. The set of congruences with $m \equiv 7 \mod1000$ give a solution $(m,n)$.

I don't know how to prove it when n is a multiple of 2 or 5. I have searched up this question, the two solutions given used dirichlet's theorem, which I can't use, and the other one didn't explain what I want to know. Thanks in advance.

Answer 1

Hint: If $m \equiv 1 \pmod{n}$, can you say anything about the gcd of $m$ and $n$?

Hint 2:

Chinese Remainder Theorem

Answer 2

If $n$ is coprime to $10$ i.e. ends with $1,3,7,9$

If $n$ is coprime to $10$, then infact there is a multiple of $n$ which ends in $006$. This is because $n$ is coprime to $1000$, therefore the remainders that $1000k + 6$ leave when divided by $n$, for $0 \leq k \leq n-1$ are all different. (If not, then $1000(k-l)$ is a multiple of $n$ for some $0 < |k-l| < n$ so $n$ must be a multiple of $1000$, a contradiction).

Therefore, for some $k$,$1000k + 6$ is a multiple of $n$. Of course, $1000k + 7$ will be coprime to $1000k+6$ and hence to $n$.

For multiples of $2$ and $5$

For numbers that are possibly multiples of $2$ and $5$, one doesn't need to think much.

Indeed, note that a number of the form $..007$ is already coprime to $2$ and $5$. Therefore, we can actually deal with a new number formed by deleting all instances of $2$ and $5$ from the prime factorization of the given number.

Indeed, if $n$ is the given number, create $l$ by removing $2$ and $5$ from the prime factorization of $n$.

Now, we can find a $..007$ which is coprime to $l$. It is also coprime to $\frac nl$, because $\frac nl$ only has $2,5$ as its prime factors, none of which divides $..007$.

Lemma

If $n$ is coprime to $a$ and coprime to $b$, then $n$ is coprime to $ab$.

To see why, $xn+ya = 1$ and $wn + zb = 1$, so multiplying , $n(xwn + xzb+yaw) + (yz)ab = 1$, so some linear combination of $n$ and $ab$ is $1$ hence their gcd is $1$.

Use of Lemma

Using the lemma, one sees that $..007$ is coprime to the product of $l$ and $\frac nl$, which is $n$!

Therefore, this $..007$ is as desired.

Examples

• Let $n = 23$. Then $n$ is coprime to $10$. Find a multiple of $23$ which ends with $006$. By what we know, one of $6,1006,...,22006$ is a multiple of $23$. We check that $12006$ is a multiple of $23$. Therefore, $12007$ is coprime to $23$.

  • Let $n = 850$. Then, $n = 17 * 50$, so our $l$ is $17$,and $\frac nl$ is $50$. We run our algorithm with $17$ : we know that one of $6,1006,2006,...,16006$ is a multiple of $17$. You can check that $2006$ is a multiple of $17$. Hence, $2007$ is coprime to $17$, and hence to $850$.