Find all positive integers n such that 20n+2 can divide 2003n+2002

Question

Could someone give me a hint to this problem please? Here is what I do: $2003n+2002=100(20n+2)+3n+1802$ then I'm stuck at $20n+2|3n+1802$ Please help

Answer 1

According to Euclid's algorithm, $\gcd(a, b) = \gcd(b, a \% b)$ where percent is modulo

$$20n+2|2003n+2002 \implies \gcd(20n+2,2003n+2002)=20n+2$$

The GCD equals

$$\gcd(20n+2, (2003n+2002)-100(20n+2))$$

$$=\gcd(20n+2,3n+1802)$$

$$=\gcd(3n+1802, 20n+2-6(3n+1802)$$

$$=\gcd(3n+1802, 2n-10810)$$

$$=\gcd(2n-10810, n+12612)$$

$$=\gcd(n+12612, -36034)=20n+2$$

Therefore $20n+2$ is a factor of $36034=2\times43\times419$ (positive)

$$20n+2=1, 2, 43, 86, 419, 838, 18017, 36034$$

As you can see, none of them end with "2" except 2. However since $n$ is positive, $20n+2\neq2$

Therefore, there're no positive integers $n$ that satisfy $20n+2|2003n+2002$.

Answer 2

If integer $d$ divides both $3n+1802, 20n+2$

$d$ must divide $20(3n+1807)-3(20n+2)=36134$

So, $20n+2$ must divide $36134$

$\iff10n+1$ divide $18067$ whose factors are $1,7,29,89,203,623,2581,18067$ none of which if of the form $10n+1$ for integer $n>0$