Maths Olympiad Prep

Library / /1 of 12

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 3x2y3^{x} - 2^{y} if and only if 2323 divides 4x+y4x + y.

Solution

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

On the other hand, we have 22349237461(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+y12^{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,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.