5.2 Arithmetic 2535.2 Arithmetic....................................................
5.2.1 Factorization and Divisibility
There isn’t much to say here. An integerddivides another integernif there is an integer
d′such thatn=dd′. In this casedis called a divisor ofn. We denote by gcd(a, b)
the greatest common divisor ofaandb. For any positive integersaandb, Euclid’s
algorithm yields integersxandysuch thatax−by =gcd(a, b). Two numbers are
called coprime, or relatively prime, if their greatest common divisor is 1. The fact that
for coprime numbersaandbthere exist integersxandysuch thatax−by=1 is called
the fundamental theorem of arithmetic.
We begin with a problem from the Soviet Union Mathematical Olympiad for Uni-
versity Students in 1976.
Example.Prove that there is no polynomial with integer coefficientsP(x)with the prop-
erty thatP( 7 )=5 andP( 15 )=9.
Solution.Assume that such a polynomialP(x)=anxn+an− 1 xn−^1 +···+a 0 does exist.
ThenP( 7 )=an 7 n+an− 17 n−^1 +···+a 0 andP( 15 )=an 15 n+an− 115 n−^1 +···+a 0.
Subtracting, we obtain
4 =P( 15 )−P( 7 )=an( 15 n− 7 n)+an− 1 ( 15 n−^1 − 7 n−^1 )+···+a 1 ( 15 − 7 ).Since for anyk,15k− 7 kis divisible by 15− 7 =8, it follows thatP( 15 )−P( 7 )= 4
itself is divisible by 8, a contradiction. Hence such a polynomial does not exist.
The second problem was given at the Asia-Pacific Mathematical Olympiad in 1998.Example.Show that for any positive integersaandb, the product( 36 a+b)(a+ 36 b)
cannot be a power of 2.
Solution.Assume that( 36 a+b)(a+ 36 b)is a power of 2 for some integersaandb.
Without loss of generality, we may assume thataandbare coprime anda<b. Let
36 a+b = 2 manda+ 36 b= 2 n. Adding and subtracting, we obtain 37(a+b)=
2 m( 2 n−m+ 1 ), respectively, 35(a−b)= 2 m( 2 n−m− 1 ). It follows that botha+band
a−bare divisible by 2m. This can happen only if bothaandbare divisible by 2m−^1.
Our assumption thataandbare coprime implies thatm=1. But then 36a+b=2,
which is impossible. Hence the conclusion.
724.Find the integersnfor which(n^3 − 3 n^2 + 4 )/( 2 n− 1 )is an integer.
725.Prove that in the productP= 1 !· 2 !· 3 !··· 100 !one of the factors can be erased so
that the remaining product is a perfect square.