# Number Theory Linear Diophantine Equations

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.

• A sophisticated approach might invoke Dirichlet's theorem on primes in arithmetic sequences. To help Readers respond in ways that are well suited to your study, more context is important, as when you state that you cannot use Dirichlet's result. – hardmath May 5 '18 at 2:21
• Let $P$ be the largest power of $7$ that divides $n$. Then $m=1000n/P+7$ works. – Macavity May 5 '18 at 2:26
• how would you prove that it works? – Glen Jiang May 5 '18 at 2:33

## 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$.
• "product of $l$ and $\frac nl$, which is $n!$" I took a double take at this! – B. Mehta May 5 '18 at 3:08

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

Hint 2:

Chinese Remainder Theorem

• hint #1 gcd(m,n)=1 hint #2 CRT tells us that there exists one unique solution, but how can I use it? – Glen Jiang May 5 '18 at 2:08
• Yup, exactly. Can you finish it off from there? – B. Mehta May 5 '18 at 2:09
• No. How does gcd(m,n)=1 help me solve the question? – Glen Jiang May 5 '18 at 2:10
• CRT gives you that there's a family of solutions to $m = 7 \pmod{1000}$, $m = 1 \pmod{n}$. – B. Mehta May 5 '18 at 2:12
• doesn't CRT only work if the numbers are not relatively prime? – Glen Jiang May 5 '18 at 2:18