Lemma:For any integers http://data.artofproblemsolving.com/images/latex/f/7/a/f7af18440f787ee3fa9f2a7dae2366ec21face9f.gif , if http://data.artofproblemsolving.com/images/latex/0/9/a/09afd859edc6b1a1a0dfb9013eaaba07bf664c90.gif ,then http://data.artofproblemsolving.com/images/latex/b/0/4/b04553c7bbe2fd65695cef132f494c94311b7b25.gif for any http://data.artofproblemsolving.com/images/latex/f/c/7/fc7ada6ca24ce5d53eb0e8b50f7db7a0801dcfd2.gif .
Proof: If http://data.artofproblemsolving.com/images/latex/b/0/4/b04553c7bbe2fd65695cef132f494c94311b7b25.gif , then we have
http://data.artofproblemsolving.com/images/latex/7/1/5/715b9fd51f6b84159b85852352c024260af64b3d.gif ①
http://data.artofproblemsolving.com/images/latex/f/1/b/f1b44c4b0bba160d5e4e8a662ae172c487bce082.gif ②
http://data.artofproblemsolving.com/images/latex/c/f/c/cfc7458ceebe928b3deaf5df50aa8f098bb5cfa8.gif ③
http://data.artofproblemsolving.com/images/latex/0/1/b/01bb84ad1b1ec62febd6b60828cd5216e448b6c9.gif ④
From ①、③ http://data.artofproblemsolving.com/images/latex/9/d/2/9d204350c7d93745c6c3aad96174a41c30801a04.gif ; from ②、④ we have http://data.artofproblemsolving.com/images/latex/b/9/4/b94274896233fbac2e3eedff6e50d769c8aa7b65.gif .
Because for http://data.artofproblemsolving.com/images/latex/1/a/b/1ab74059871c14599195cf4fc3c5c5dca2bc643d.gif , http://data.artofproblemsolving.com/images/latex/0/9/a/09afd859edc6b1a1a0dfb9013eaaba07bf664c90.gif , so we done.

Solution: Obviously http://data.artofproblemsolving.com/images/latex/3/6/1/361e4570df4668768772c6597a09c95d704c6a93.gif satisfies the condition.
Next we suppose http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif has at least two elements, denotes http://data.artofproblemsolving.com/images/latex/1/1/9/119e86e5bc3bd57d20c87a00e0976f93bc2f0970.gif , then there exits a integer http://data.artofproblemsolving.com/images/latex/8/6/f/86f7e437faa5a7fce15d1ddcb9eaeaea377667b8.gif satisfies http://data.artofproblemsolving.com/images/latex/0/9/a/09afd859edc6b1a1a0dfb9013eaaba07bf664c90.gif . By the lemma http://data.artofproblemsolving.com/images/latex/3/a/1/3a1d2b80d714d8da9669e0ec277a18a1bc3d8431.gif .
It is easy to check that http://data.artofproblemsolving.com/images/latex/6/d/0/6d0f94fb622d1e3e3707b351cf3c6cf1b0353132.gif satisfies the condition.
If http://data.artofproblemsolving.com/images/latex/a/2/c/a2ce3c20e0eddc2c45c5598bf1275ac5a41b7ab1.gif , there exits a integer http://data.artofproblemsolving.com/images/latex/b/9/0/b906f13625ef22266db594817773f28a3e096083.gif , then there exits a integer http://data.artofproblemsolving.com/images/latex/4/d/c/4dc7c9ec434ed06502767136789763ec11d2c4b7.gif , that http://data.artofproblemsolving.com/images/latex/4/3/d/43da499b5b13e48ae5b4e8143826b358f0829425.gif , for the minimality of http://data.artofproblemsolving.com/images/latex/c/2/c/c2c53d66948214258a26ca9ca845d7ac0c17f8e7.gif , http://data.artofproblemsolving.com/images/latex/c/b/5/cb59545c4894f7be6cb81fd658be1b9702b03d84.gif .
Because http://data.artofproblemsolving.com/images/latex/1/4/6/1462c43559b41d66b97ea16dc0017dcbb4a6ff76.gif , by the lemma http://data.artofproblemsolving.com/images/latex/b/7/7/b77552ab40fe81bfb7bc0188756dc7e30f257a48.gif , so http://data.artofproblemsolving.com/images/latex/9/9/6/996a8caf05f5eea9df1da44e52727d3935f14ecb.gif .
There three types http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif :
a)http://data.artofproblemsolving.com/images/latex/1/4/c/14c8573597a0feade9618a59fb9e61d17739b617.gif;
b)http://data.artofproblemsolving.com/images/latex/9/c/3/9c3a73dc476df66c7bd8972a0983b1659c96fd44.gif for any positive integer http://data.artofproblemsolving.com/images/latex/c/2/c/c2c53d66948214258a26ca9ca845d7ac0c17f8e7.gif and integer http://data.artofproblemsolving.com/images/latex/8/6/f/86f7e437faa5a7fce15d1ddcb9eaeaea377667b8.gif ;
c) http://data.artofproblemsolving.com/images/latex/5/a/8/5a8e5b52663a458e141eaf17ddfdb9c132a409a0.gif for any positive integer http://data.artofproblemsolving.com/images/latex/c/2/c/c2c53d66948214258a26ca9ca845d7ac0c17f8e7.gif and integer http://data.artofproblemsolving.com/images/latex/8/6/f/86f7e437faa5a7fce15d1ddcb9eaeaea377667b8.gif .

http://s5/mw690/4c113102gd32071bc1814&690

解答（上海 veyron）http://data.artofproblemsolving.com/images/latex/c/7/e/c7eb9c7f0da8f1dde925f519f76101c3ad3a9a20.gif .

Firstly, we show that for any infinite set X, there exists http://data.artofproblemsolving.com/images/latex/f/2/e/f2edf287c864c61df95b6675265d0045500ffb2c.gif , http://data.artofproblemsolving.com/images/latex/a/8/6/a86071b1fa5e37b53788f5fa626f033cc296cb7b.gif s.t. http://data.artofproblemsolving.com/images/latex/c/0/c/c0c6ff3f4c05a406d4cff429a46eb6efc8adda5f.gif
We can choose http://data.artofproblemsolving.com/images/latex/c/e/e/ceed75c8dadde69cae24c37570bbd5dccb0859e3.gif and see that http://data.artofproblemsolving.com/images/latex/b/4/6/b46882f8e179adad9fd6311d75f174fced977d44.gif .

Secondly, we show that for any http://data.artofproblemsolving.com/images/latex/c/7/e/c7eb9c7f0da8f1dde925f519f76101c3ad3a9a20.gif , if we choose http://data.artofproblemsolving.com/images/latex/5/2/5/52504c42556e5f6afa430b05b6ae25b0ae40ed73.gif (k is positive integers) , then for any http://data.artofproblemsolving.com/images/latex/f/2/e/f2edf287c864c61df95b6675265d0045500ffb2c.gif , http://data.artofproblemsolving.com/images/latex/7/b/4/7b499fc4baa61a94cf4341b2a2c3a883885bd6d2.gif http://data.artofproblemsolving.com/images/latex/c/6/5/c65bbfed3c403eeca5040ca70e6adfca9ae4ad7c.gif .
1)if http://data.artofproblemsolving.com/images/latex/2/1/2/2122bac1f4247c9a9ffe5dc55e67976b637e11b4.gif , then
http://data.artofproblemsolving.com/images/latex/e/0/e/e0e21c01d779d157ed24ce3dad7eef400b5a6c28.gif , so http://data.artofproblemsolving.com/images/latex/b/8/c/b8c9f075aad96001478dbe8d78f8005fb3a5cd5e.gif
2)if http://data.artofproblemsolving.com/images/latex/c/d/9/cd9bd92de80cb00cffbb8d722149dffd4698b8c1.gif , then
http://data.artofproblemsolving.com/images/latex/2/e/8/2e8ec980c79613a064cef66bbb386bf72b6c443b.gif , so http://data.artofproblemsolving.com/images/latex/e/3/1/e31d0de073ec259a655ee98ecb713742cfef904f.gif
3)if http://data.artofproblemsolving.com/images/latex/b/6/c/b6ce4f035dd40007169942973b93d8b6b7a660ad.gif , then
http://data.artofproblemsolving.com/images/latex/b/7/1/b71c7960864d3467bca4672098352692f053544f.gif , so http://data.artofproblemsolving.com/images/latex/b/8/c/b8c9f075aad96001478dbe8d78f8005fb3a5cd5e.gif
4)http://data.artofproblemsolving.com/images/latex/9/f/9/9f9ddc81681bf96e846d822b267968e25608095b.gif are distinct. Suppose the contrary, then
http://data.artofproblemsolving.com/images/latex/8/b/2/8b2449d16966d7fabc4103deaa569ad3657d7798.gif ,http://data.artofproblemsolving.com/images/latex/b/5/3/b531719ecca344832835ed168851e0981ee5aa74.gif, we can conclude that
http://data.artofproblemsolving.com/images/latex/4/4/d/44d61b7e40e189d2ab9073697dcac4bde3c2adf9.gif .
This is impossible, since http://data.artofproblemsolving.com/images/latex/4/d/c/4dc046321b0a625d0c3afe175b870f77cfd95e43.gif ,http://data.artofproblemsolving.com/images/latex/c/3/5/c35722a6e715c531dffdbd34bfbf53ffdb27b4fe.gif, on the other hand,
http://data.artofproblemsolving.com/images/latex/d/1/c/d1c652a621b2c79e516e49db8b424fbf4ba8fc97.gif , a contradiction.

 

迄今为此所有CMO第三题中，数此题最简单。（veyron）

http://s9/mw690/4c113102gd33c450a38e8&690
http://s12/mw690/4c113102gd33c4608b13b&690

http://s1/mw690/4c113102gd33b87314ed0&690
解答（SnowEverywhere）
Consider the polynomial http://data.artofproblemsolving.com/images/latex/f/8/e/f8eb773889d020c62b57df26243860386a09ec8f.gif where the binary representation of http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif is http://data.artofproblemsolving.com/images/latex/0/0/5/00502d8a861d068266fb146fb1b800aa2196cb82.gif where http://data.artofproblemsolving.com/images/latex/4/4/f/44f122917241596e1c567157aec94e6e3f3473fe.gif . By definition, it follows that http://data.artofproblemsolving.com/images/latex/4/c/a/4cab634b9d79ef5e1f04e703c7ed622b2fcb4465.gif . Now examine the product http://data.artofproblemsolving.com/images/latex/2/f/b/2fbde11e74037fc73996156450dff3486ec883e9.gif . Now note that for each nonnegative integer http://data.artofproblemsolving.com/images/latex/0/4/2/042dc4512fa3d391c5170cf3aa61e6a638f84342.gif , it follows that http://data.artofproblemsolving.com/images/latex/8/3/a/83a2c323071c74ce79e99fba08fd8cfc7dbd48ae.gif . Therefore the product above is congruent to http://data.artofproblemsolving.com/images/latex/d/5/a/d5aeff773ff5c742988b8715c11aaa485385f108.gif in modulo http://data.artofproblemsolving.com/images/latex/d/a/4/da4b9237bacccdf19c0760cab7aec4a8359010b0.gif and therefore to http://data.artofproblemsolving.com/images/latex/9/5/1/9516c6d068c67c33cad7069f861fa021c58d3719.gif . Viewing the product as a generating function of http://data.artofproblemsolving.com/images/latex/1/1/f/11f6ad8ec52a2984abaafd7c3b516503785c2072.gif yields that the coefficients of the expansion are each either http://data.artofproblemsolving.com/images/latex/b/6/5/b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.gif or equal to http://data.artofproblemsolving.com/images/latex/3/5/6/356a192b7913b04c54574d18c28d46e6395428ab.gif if the corresponding term http://data.artofproblemsolving.com/images/latex/b/e/a/bea96aff8355175946f975fbe5951ef62ccc4d10.gif satisfies that http://data.artofproblemsolving.com/images/latex/0/4/2/042dc4512fa3d391c5170cf3aa61e6a638f84342.gif has binary digits in a set of positions that are a subset of http://data.artofproblemsolving.com/images/latex/5/3/2/53289a0f2446c220ce6e6f29cf5dfbb941f1957f.gif . Therefore the coefficients of this product are each either http://data.artofproblemsolving.com/images/latex/b/6/5/b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.gif or http://data.artofproblemsolving.com/images/latex/3/5/6/356a192b7913b04c54574d18c28d46e6395428ab.gif which implies that the product is equal to http://data.artofproblemsolving.com/images/latex/9/5/1/9516c6d068c67c33cad7069f861fa021c58d3719.gif .

Now consider http://data.artofproblemsolving.com/images/latex/7/4/7/747194864ed558f79fd2bda53a58ed721802440b.gif and http://data.artofproblemsolving.com/images/latex/f/0/b/f0b17e650abd4f92be5b0b637ed9f1d4f92c482e.gif . By the given condition, http://data.artofproblemsolving.com/images/latex/b/0/8/b08b93a583a6ac7022dd79980f7142e83614fed5.gif . As shown above, each can be expressed as the product of terms of the form http://data.artofproblemsolving.com/images/latex/f/c/e/fcef43fa7c696276e34b921d0f2d592b0cc3835b.gif . For any two distinct such terms, reducing the larger one modulo the smaller one yields that their greatest common divisor divides http://data.artofproblemsolving.com/images/latex/d/a/4/da4b9237bacccdf19c0760cab7aec4a8359010b0.gif . If http://data.artofproblemsolving.com/images/latex/7/1/6/7169b41380ffc9ba051c2737eade95e614d60f99.gif , then as given, http://data.artofproblemsolving.com/images/latex/d/5/c/d5c98c326805028ac8c16b6bae65b63deaf92f05.gif is not a power of http://data.artofproblemsolving.com/images/latex/d/a/4/da4b9237bacccdf19c0760cab7aec4a8359010b0.gif and thus has an odd prime divisor http://data.artofproblemsolving.com/images/latex/5/1/6/516b9783fca517eecbd1d064da2d165310b19759.gif . Similarly, if http://data.artofproblemsolving.com/images/latex/2/b/a/2ba8f62a529123aa4b61e59184fdf53d7da5f251.gif , then http://data.artofproblemsolving.com/images/latex/4/9/0/4909af4e07f0da73f91ed0536160e2c762cd8156.gif and thus, since http://data.artofproblemsolving.com/images/latex/b/0/8/b08b93a583a6ac7022dd79980f7142e83614fed5.gif , must have an odd prime divisor http://data.artofproblemsolving.com/images/latex/5/1/6/516b9783fca517eecbd1d064da2d165310b19759.gif as well. Thus if any such term in the product representation of http://data.artofproblemsolving.com/images/latex/7/4/7/747194864ed558f79fd2bda53a58ed721802440b.gif does not appear in the representation of http://data.artofproblemsolving.com/images/latex/f/0/b/f0b17e650abd4f92be5b0b637ed9f1d4f92c482e.gif , it has an odd prime divisor http://data.artofproblemsolving.com/images/latex/5/1/6/516b9783fca517eecbd1d064da2d165310b19759.gif that cannot divide any term in the product representation of http://data.artofproblemsolving.com/images/latex/f/0/b/f0b17e650abd4f92be5b0b637ed9f1d4f92c482e.gif (since the greatest common divisor of any two terms divides http://data.artofproblemsolving.com/images/latex/d/a/4/da4b9237bacccdf19c0760cab7aec4a8359010b0.gif ). This is a contradiction and, by examining the formula for http://data.artofproblemsolving.com/images/latex/9/5/1/9516c6d068c67c33cad7069f861fa021c58d3719.gif shown above, implies that every digit in the binary representation of http://data.artofproblemsolving.com/images/latex/6/b/0/6b0d31c0d563223024da45691584643ac78c96e8.gif also appears in the binary representation of http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif . By this same formula, it follows that http://data.artofproblemsolving.com/images/latex/3/8/3/3838a459f6c38a46a96ca252f8b35a9efd65bfe6.gif divides http://data.artofproblemsolving.com/images/latex/e/a/d/ead11fcc21daac0c9f9cfcc2594da7e6cc932d3a.gif for all positive integers http://data.artofproblemsolving.com/images/latex/4/d/c/4dc7c9ec434ed06502767136789763ec11d2c4b7.gif .

http://s8/mw690/4c113102gd354237285b7&690
http://data.artofproblemsolving.com/images/latex/f/4/3/f43079fb64939a3f55c190bcce1b29fa0e482290.gif are positive integers, find the minimum positive integer http://data.artofproblemsolving.com/images/latex/b/5/1/b51a60734da64be0e618bacbea2865a8a7dcd669.gif satisties that if http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif is a set of integers contains a complete residue system of http://data.artofproblemsolving.com/images/latex/6/b/0/6b0d31c0d563223024da45691584643ac78c96e8.gif and http://data.artofproblemsolving.com/images/latex/3/b/3/3b38096a01b88b8d28fe7d0e44528e22eeaed35f.gif , then there exit a nonempty set http://data.artofproblemsolving.com/images/latex/0/a/3/0a3a832acad646073f39cec542e57612d68c340a.gif , that http://data.artofproblemsolving.com/images/latex/b/6/a/b6ace8a506dc74ead365a61c606dee5a5c61f47b.gif .

解答（宁波 zhaobin）

It maybe a hard problem.But when you compare this problem to the famous(Lemma 1),you will have a approach to combine them.The nice ideas you must pairs the residue of http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif when http://data.artofproblemsolving.com/images/latex/c/2/f/c2f0484b28de71784a5ac889a9b0fc68c345e3ec.gif .

The answer is http://data.artofproblemsolving.com/images/latex/9/b/9/9b9eadab31951ff1dffbbe6ae01abe02c8e5f099.gif Where http://data.artofproblemsolving.com/images/latex/f/5/6/f566d3df41e298b9cab642d84cc4d4b546932f31.gif is the greatest common divsor of integer http://data.artofproblemsolving.com/images/latex/6/b/0/6b0d31c0d563223024da45691584643ac78c96e8.gif and http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif .

Lemma 1:For any positive integer http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif ,and any integers http://data.artofproblemsolving.com/images/latex/1/c/7/1c76c5486123a0b7c89f1807588800fa5b440ecf.gif ,then there exist an nonempty set http://data.artofproblemsolving.com/images/latex/c/a/7/ca73ab65568cd125c2d27a22bbd9e863c10b675d.gif of http://data.artofproblemsolving.com/images/latex/9/7/c/97cd63bdaf2c23cfe3ab54e36ef08c7c88d7205b.gif ,such that http://data.artofproblemsolving.com/images/latex/5/1/a/51a009e48b817f57ee354644cc213e54bf55a112.gif

Lemma 2:For any positive even integer http://data.artofproblemsolving.com/images/latex/d/1/8/d1854cae891ec7b29161ccaf79a24b00c274bdaa.gif ,and any integers http://data.artofproblemsolving.com/images/latex/9/f/c/9fcfc75ecb7b3ba7fb02dc6673c21b863ded0041.gif andhttp://data.artofproblemsolving.com/images/latex/6/4/5/645e74c82f829a0368a400e4c7c0e17ca8d46f40.gif.then there exist an nonempty set http://data.artofproblemsolving.com/images/latex/c/a/7/ca73ab65568cd125c2d27a22bbd9e863c10b675d.gif of http://data.artofproblemsolving.com/images/latex/2/a/c/2aca36a8d8edf6f1acc9969e751f39a2103ecee3.gif ,such that http://data.artofproblemsolving.com/images/latex/5/1/a/51a009e48b817f57ee354644cc213e54bf55a112.gif (Proof of Lemma 1 and 2 is left for you.)

Back to the orginal problem.Suppose http://data.artofproblemsolving.com/images/latex/9/8/9/98909b09af77928806762bb1188f9a97617b4e88.gif .
(a)http://data.artofproblemsolving.com/images/latex/3/c/3/3c363836cf4e16666669a25da280a1865c2d2874.gif is an odd integer,
(i)when http://data.artofproblemsolving.com/images/latex/a/1/2/a12d82c1e81c256505a82db5908dc6f96ea1bc9d.gif ,we shall prove for any set http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif contains a complete residue system of http://data.artofproblemsolving.com/images/latex/6/b/0/6b0d31c0d563223024da45691584643ac78c96e8.gif ,then there exit a nonempty set http://data.artofproblemsolving.com/images/latex/0/a/3/0a3a832acad646073f39cec542e57612d68c340a.gif , that http://data.artofproblemsolving.com/images/latex/b/6/a/b6ace8a506dc74ead365a61c606dee5a5c61f47b.gif .Let's do this.Suppose http://data.artofproblemsolving.com/images/latex/6/6/0/6601d61337a7b2591b586f25a7298ddf22092cc6.gif such that
http://data.artofproblemsolving.com/images/latex/5/2/6/5265f8ff6ad57a993dc00fe1658a5bdff68bddd8.gif
then we have
http://data.artofproblemsolving.com/images/latex/c/4/d/c4d4d06dd539a5d33de5ea9c892b46f40cfa0677.gif
http://data.artofproblemsolving.com/images/latex/6/7/5/6750868a5de025935149f8b02e31801b40082e4d.gif
http://data.artofproblemsolving.com/images/latex/7/8/3/7835130167f163c1fc24470f60ac6ec166aea61e.gif
http://data.artofproblemsolving.com/images/latex/8/e/d/8ed2c01f0f9a66a43571e23a1b09eba279725e9c.gif
http://data.artofproblemsolving.com/images/latex/6/7/3/67324232ab2ff332b2cc74cf60027510f18661c8.gif
http://data.artofproblemsolving.com/images/latex/0/b/2/0b2002656c348b17d48de11fffce694be644984a.gif
Because http://data.artofproblemsolving.com/images/latex/f/0/3/f03eb643b992a2698213a1e4e429c962cfd465f4.gif are all multiplies of http://data.artofproblemsolving.com/images/latex/3/c/3/3c363836cf4e16666669a25da280a1865c2d2874.gif ,we can set http://data.artofproblemsolving.com/images/latex/6/7/3/673e279b8b37a2eabc8608684169c2171458df37.gif ,and with http://data.artofproblemsolving.com/images/latex/4/5/3/453ccbc34773f84ae40dbb3c75a207088170b701.gif .
By Lemma 1 we can find and nonempty subset http://data.artofproblemsolving.com/images/latex/c/a/7/ca73ab65568cd125c2d27a22bbd9e863c10b675d.gif of http://data.artofproblemsolving.com/images/latex/1/8/3/183be4fc5056ee0c0d2c6c156eed98fe47f61296.gif ,such that,http://data.artofproblemsolving.com/images/latex/f/5/6/f565f86e4e651c18f8713795556b2965957f4c78.gif,which means http://data.artofproblemsolving.com/images/latex/a/d/c/adc99b541f10bd28f054d0889dcc8639f105237f.gif .Which complete the solution in this case.

(ii)when http://data.artofproblemsolving.com/images/latex/a/7/d/a7d61cf0f78d8f95f15ad71370cb358a956fa930.gif ,then when http://data.artofproblemsolving.com/images/latex/4/8/4/48443bf915d1349e6c531bdd3ab917a4cfd624f6.gif .Set http://data.artofproblemsolving.com/images/latex/e/3/c/e3c67ab649521ab4946740d78228536414ea30aa.gif and http://data.artofproblemsolving.com/images/latex/4/e/4/4e4a017a752f7c824ac6ce26096c590b51572550.gif as in case (i),let http://data.artofproblemsolving.com/images/latex/f/7/5/f754b5352e232a2c0fe045e078b31ab2af42c7a8.gif .And in this case there left at least http://data.artofproblemsolving.com/images/latex/a/c/f/acff7343c2bc4a242267cc1a0887bd7a8fce045a.gif in http://data.artofproblemsolving.com/images/latex/8/d/8/8d89fb971842d1e18476a5269319335870e5fdf1.gif ,by Lemma 1 some times we can prove there exist nonempty subsets http://data.artofproblemsolving.com/images/latex/b/9/4/b949888bb8447880e43bbb59081b8ba790304621.gif (with empty intersection) of http://data.artofproblemsolving.com/images/latex/8/d/8/8d89fb971842d1e18476a5269319335870e5fdf1.gif such that http://data.artofproblemsolving.com/images/latex/1/4/9/14982831732be0187b36fad9d28ca49b3772b557.gif are all multiplies of http://data.artofproblemsolving.com/images/latex/3/c/3/3c363836cf4e16666669a25da280a1865c2d2874.gif .Set http://data.artofproblemsolving.com/images/latex/c/5/a/c5a0e58bc6b4b5d3ecdf85d2f97ffc0e293c40a9.gif .Again by Lemma 1,we can find and nonempty subset http://data.artofproblemsolving.com/images/latex/c/a/7/ca73ab65568cd125c2d27a22bbd9e863c10b675d.gif of http://data.artofproblemsolving.com/images/latex/9/7/c/97cd63bdaf2c23cfe3ab54e36ef08c7c88d7205b.gif ,such that,http://data.artofproblemsolving.com/images/latex/f/5/6/f565f86e4e651c18f8713795556b2965957f4c78.gif,which means http://data.artofproblemsolving.com/images/latex/a/d/c/adc99b541f10bd28f054d0889dcc8639f105237f.gif ,which means we can find a nonempty set http://data.artofproblemsolving.com/images/latex/6/d/c/6dcd4ce23d88e2ee9568ba546c007c63d9131c1b.gif of http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif such that http://data.artofproblemsolving.com/images/latex/e/5/c/e5ce90593878bc785bc83e5f4a8a07b8e101dbbd.gif .

And for http://data.artofproblemsolving.com/images/latex/5/3/2/53220fcfcfbf81ba71b2fd4c71a7e8c58f340cfe.gif ,let http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif consists of http://data.artofproblemsolving.com/images/latex/1/e/7/1e768fc30e7a8e8cedb0e6b951baa99728def19d.gif ,and the other http://data.artofproblemsolving.com/images/latex/f/2/7/f27f1b6ae66beb6c65d284fef3c58b10699c72e3.gif such that http://data.artofproblemsolving.com/images/latex/f/6/7/f67f2275abd24f411f9017bb9b804cddd2eca616.gif .Then http://data.artofproblemsolving.com/images/latex/0/2/a/02aa629c8b16cd17a44f3a0efec2feed43937642.gif is an example.

(b)http://data.artofproblemsolving.com/images/latex/3/c/3/3c363836cf4e16666669a25da280a1865c2d2874.gif is an even integer.I'm tired to write solution in this case,In this case the http://data.artofproblemsolving.com/images/latex/f/5/0/f50d06328d8d076870d59691bb4b30fcf23c8f08.gif may can't be pairs,we can use Lemma 2 in somewhere to complete the solution.