Browse · MathNet
PrintXI 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).
(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