Problem:
Let S be a set of integers (not necessarily positive) such that
A. there exist a,bβS with gcd(a,b)=gcd(aβ2,bβ2)=1;
B. if x and y are elements of S (possibly equal), then x2βy also belongs to S.
Prove that S is the set of all integers.
Solution:
In the solution below we use the expression S is stable under xβ¦f(x) to mean that if x belongs to S then f(x) also belongs to S. If c,dβS, then by (B), S is stable under xβ¦c2βx and xβ¦d2βx, hence stable under xβ¦c2β(d2βx)=x+(c2βd2). Similarly S is stable under xβ¦x+(d2βc2). Hence S is stable under xβ¦x+n and xβ¦xβn whenever n is an integer linear combination of numbers of the form c2βd2 with c,dβS. In particular, this holds for n=m, where
m=gcd{c2βd2:c,dβS}
Since Sξ =β
by (A), it suffices to prove that m=1. For the sake of contradiction, assume that mξ =1. Let p be a prime dividing m. Then c2βd2β‘0(modp) for all c.dβS. In other words, for each c,dβS, either dβ‘c(modp) or dβ‘βc(modp). (iiven cβS. c2βcβS by (B), so c2βcβ‘c(modp) or c2βcβ‘βc(modp). Hence
For each cβS, either cβ‘0(modp) or cβ‘2(modp). (*)
By (A), there exist some a and b in S such that gcd(a,b)=1, that is, at least one of a or b cannot be divisible by p. Denote such an element of S by Ξ± : thus, aξ =0 (mod p ). Similarly, by (A),gcd(aβ2,bβ2)=1, so p cannot divide both aβ2 and bβ2. Thus. there is an element of S, call it Ξ², such that Ξ²ξ β‘2(modp). By (β),Ξ±β‘2(modp) and Ξ²β‘0(modp).By(B),Ξ²2βΞ±βS. Taking c=Ξ²2βΞ± in (β) yields cither β2β‘0 (modp) or β2β‘2(modp), so p=2. Now (β) says that all elements of S are even, contradicting (A). Hence our assumption is false and S is the set of all integers.
The problems on this page are the property of the MAA's American Mathematics Competitions