Name: Counting With Bijections
Uploaded: 2019-07-19
Duration: 11 min 43 s
Description: In this informative video, you will learn about the Bijection principle in algebra. Let's watch, understand and master this concept right away!

Question

There are seventeen distinct positive integers such that none of them has a prime factor exceeding

10

. Show that the product of some two of them is a square.

Accepted Answer

Since none of the $17$ integers has a prime factor exceeding $10$ , all of them have the form $2^{a} 3^{b} 5^{c} 7^{d}$ , where $a, b, c$ and $d$ are non-negative integers. The product two such numbers, say $2^{a} 3^{b} 5^{c} 7^{d}$ and $2^{a^{'}} 3^{b^{'}} 5^{c^{'}} 7^{d^{'}}$ , is

$(2^{a} 3^{b} 5^{c} 7^{d}) (2^{a^{'}} 3^{b^{'}} 5^{c^{'}} 7^{d^{'}}) = 2^{a + a^{'}} 3^{b + b^{'}} 5^{c + c^{'}} 7^{d + d^{'}}$ .

Thus if $a + a^{'}, b + b^{'}, c + c^{'}$ and $d + d^{'}$ are all even then the product would be a square. For this to happen the $4$ -tuples $(a, b, c, d)$ and $(a^{'}, b^{'}, c^{'}, d^{'})$ should have the same parity (that is to say $a$ and $a^{'}$ should both be odd or both even, $b$ and $b^{'}$ should be both odd or both even etc.). Since each of the numbers $a, b, c$ and $d$ can either be odd or even, the total number of patterns of the $4$ -tuples $(a, b, c, d)$ is $2^{4} = 16$ . As we have seventeen $4$ -tuples $(a, b, c, d)$ , each corresponding to the $17$ given numbers, it follows, by the pigeon-hole principle, that at least two of these seventeen $4$ -tuples should have the same parity. The product of the numbers corresponding to these $4$ -tuples will then be a square.

There are seventeen distinct positive integers such that none of them has a prime factor exceeding $10$ . Show that the product of some two of them is a square.

Important Questions on Combinatorics

Learn and Prepare for any exam you want !

There are seventeen distinct positive integers such that none of them has a prime factor exceeding 10. Show that the product of some two of them is a square.

Important Questions on Combinatorics

Learn and Prepare for any exam you want !

There are seventeen distinct positive integers such that none of them has a prime factor exceeding $10$ . Show that the product of some two of them is a square.