Number theoryDifficulty 7.1National olympiad, round 2Prove itSaudi Arabia
Let x,y be two non-negative integers. Prove that 47 divides 3x−2y if and only if 23 divides 4x+y.
Solution
Because 2 and 47 are relatively prime numbers, 47 divides 3x−2y if and only if 47 divides 24x(3x−2y). But 24x(3x−2y)=48x−24x+y≡1−24x+y(mod47). Therefore 47 divides 3x−2y if and only if 24x+y≡1(mod47).
On the other hand, we have 223≡4923≡746≡1(mod47). We deduce that the prime number 23 is the order of 2 modulo 47. This implies that 24x+y≡1 mod 47 if and only if 23 divides 4x+y.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic and difficulty added by this site.