270 5 Number Theory786.Prove that for everyn, there existnconsecutive integers each of which is divisible
by two different primes.
787.LetP(x)be a polynomial with integer coefficients. For any positive integerm, let
N (m)denote the number of solutions to the equationP(x)≡ 0 (modm). Show
that ifm 1 andm 2 are coprime integers, thenN(m 1 m 2 )=N(m 1 )N (m 2 ).
788.Alice and Bob play a game in which they take turns removing stones from a heap
that initially hasnstones. The number of stones removed at each turn must be
one less than a prime number. The winner is the player who takes the last stone.
Alice plays first. Prove that there are infinitely manynsuch that Bob has a winning
strategy. (For example, ifn=17, then Alice might take 6 leaving 11; then Bob
might take 1 leaving 10; then Alice can take the remaining stones to win.)
789.Show that there exists an increasing sequence(an)n≥ 1 of positive integers such that
for anyk≥0, the sequencek+an,n≥1, contains only finitely many primes.
790.Is there a sequence of positive integers in which every positive integer occurs exactly
once and for everyk= 1 , 2 , 3 ,...the sum of the firstkterms is divisible byk?
791.Prove that there exists a positive integerksuch thatk· 2 n+1 is composite for every
positive integern.
792.Letaandbbe two positive integers such that for any positive integern,an+n
dividesbn+n. Prove thata=b.
793.A lattice point(x, y)∈Z^2 is visible from the origin ifxandyare coprime. Prove
that for any positive integernthere exists a lattice point(a, b)whose distance from
every visible point is greater thann.5.3 Diophantine Equations..........................................
5.3.1 Linear Diophantine Equations..............................
A linear Diophantine equation (named in the honor of Diophantus, who studied equations
over the integers) is an equation of the form
a 1 x 1 +···+anxn=b,
wherea 1 ,...,an, andbare integers. We will discuss only the Diophantine equation
ax−by=c.
Theorem.The equationax−by =chas solutions if and only ifgcd(a, b)divides
c.If(x 0 ,y 0 )is a solution, then all other solutions are of the formx=x 0 +gcd(a,b)b t,
y=y 0 +gcd(a,b)a t,t∈Z.