Skip to main content
OlympiadHQ

Browse · MathNet

Print

XI OBM

Brazil number theory

Problem

is a positive integer such that is a square. Show that is a multiple of , and and are squares.
Solution
Suppose , so . and are coprime so either

(1) and , or

(2) and .

But (2) implies that is a square, whereas squares must be or mod . So we must have (1).

Techniques

Greatest common divisors (gcd)Quadratic residuesTechniques: modulo, size analysis, order analysis, inequalities