There is a set S of integers {1,2,⋯,100}. How many elements does the largest subset of S have so that the product of no 2 distinct elements in S is a perfect square? Prove that this is the maximum.

My idea so far is to make the subset contain 1, all the primes, all the semiprimes (numbers that are p*q where p and q are distinct primes), and all the numbers that are p*q*r where p,q,r are distinct primes. Intuitively, this seems like it would make the largest subset, but I'm not sure how to prove it.

 Sep 10, 2021

The largest number of elements in S is 20, one for each congruence class modulo 5.

 Sep 11, 2021

5 Online Users