Maths Olympiad Prep

Library / Preselection Tests for the Full-time Training /1 of 10

Preselection Tests for the Full-time Training

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Saudi Arabia

Let x,yx, y be two non-negative integers. Prove that 4747 divides 3x−2y3^{x} - 2^{y} if and only if 2323 divides 4x+y4x + y.

Solution

Because 22 and 4747 are relatively prime numbers, 4747 divides 3x−2y3^{x} - 2^{y} if and only if 4747 divides 24x(3x−2y)2^{4x}(3^{x} - 2^{y}). But
24x(3x−2y)=48x−24x+y≡1−24x+y(mod47). 2^{4x}(3^{x} - 2^{y}) = 48^{x} - 2^{4x + y} \equiv 1 - 2^{4x + y} \pmod{47}.
Therefore 4747 divides 3x−2y3^{x} - 2^{y} if and only if 24x+y≡1(mod47)2^{4x + y} \equiv 1 \pmod{47}.

On the other hand, we have 223≡4923≡746≡1(mod47)2^{23} \equiv 49^{23} \equiv 7^{46} \equiv 1 \pmod{47}. We deduce that the prime number 2323 is the order of 22 modulo 4747. This implies that 24x+y≡12^{4x + y} \equiv 1 mod 4747 if and only if 2323 divides 4x+y4x + y.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.