# Thread: Smallest positive integer

1. ## Smallest positive integer

What is the smallest positive integer that when divide by 10, 9, 8, 7, and 6 leaves the reaminders 9, 8, 7, 6 , and 5, respectively?

2. Originally Posted by ceasar_19134
What is the smallest positive integer that when divide by 10, 9, 8, 7, and 6 leaves the reaminders 9, 8, 7, 6 , and 5, respectively?
I hope you are familiar with congruences and the chinese remainder theorem.
---
The general theorem used here if,
x=a(mod pq) where gcd(p,q)=1
It is equivalent to (Euclid's Lemma),
x=a(mod p) and x=a(mod q)
Thus, by the terms of the problem,
x=9(mod 10)
x=8(mod 9)
x=7(mod 8)
x=6(mod 7)
x=5(mod 6)
Equivalently,
x+1=0(mod 2*5)
x+1=0(mod 3^2)
x+1=0(mod 2^2)
x+1=0(mod 7)
x+1=0(mod 2*3)
Equivalently,
x+1=0(mod 2) (1)
x+1=0(mod 5) (2)
x+1=0(mod 3^2) (3)
x+1=0(mod 2^2) (4)
x+1=0(mod 7) (5)
x+1=0(mod 2) (6)
x+1=0(mod 3) (7)
Equations:
(4) implies (1) and (6)
(3) implies (7)
Thus, eliminating those,
x+1=0(mod 5)
x+1=0(mod 9)
x+1=0(mod 7)
x+1=0(mod 8)
Equivalently,
x=-1 (mod 5)
x=-1 (mod 9)
x=-1 (mod 7)
x=-1 (mod 8)
And, gcd between any two is one.
Thus you can rely on Chinese Remainder Theorem