EngineeringRise

On S = 1, 2, ..., 20, a relation R is defined by a R b if the product ab is a perfect square. R is an equivalence relation. The number of ordered pairs (a, b) in R is

Answer: (B) 42 Status: Verified (T1). Checked by code and independent solves on 2026-11-20.

  1. 13
  2. 42
  3. 60
  4. 20

Solution

  1. ab is a square exactly when a and b have the same square-free part, so the classes are the square-free parts.
  2. Classes: 1,4,9,16, 2,8,18, 3,12, 5,20 and nine singletons 6,7,10,11,13,14,15,17,19.
  3. Ordered pairs = sum of (class size)² = 16 + 9 + 4 + 4 + 9 = 42. The number 13 counts classes, not pairs.

Fast method

Pairs in an equivalence relation = sum of squares of class sizes: 16 + 9 + 4 + 4 + 9 x 1 = 42.

Expected time: about 170 seconds. Difficulty: hard.

Topic page: Relations and equivalence relations

Test your answers now

Report an error

Think the question, answer or a step is wrong? One tap tells us. We check it and publish the correction.