Let n be a positive integer. 1. Prove that if you have n +1 positive integers le
ID: 3599542 • Letter: L
Question
Let n be a positive integer. 1. Prove that if you have n +1 positive integers less than or equal to 2n, you can always find two of them which are relatively prime, (i.e., they do not share any common factor) 2. Prove that if you have n +1 positive integers less than or equal to 2n, you can also find two of them such that one will divide the other. 3. Find an integer n 22 such that both of the above assertions are false for a set of only n integers (you may have a different set for each of the above assertions). Note. When Lajos Posa, one of the most porminent mathematics educator in Hungary currently, was a child, poeple already noted his mathematical talent. At that time the international famed mathematician, Paul Erdos, heard about Posa, Erdos invited Posa for a lunch. While they were eating soup, Erdos was able to give a very elegant solution about half-minutes. At that time, Posa was only 12 years old. gave Posa the first problem above and Posa Hint for the Second Problem: Write each of the n + 1 positive integers in the form 2 m for some integers k and m, where m is an odd integer 1. Since all the integers are less than or equal to 2n, the odd part m for each of the integers can only be an odd integer between 1 and 2n. How many odd integers can there be between 1 and 2n? ).Explanation / Answer
Solution:
Two integers are are said to be relatively prime if they do not share any common factor or there is no integer greater than one that divides both of them.
We have a set of n positive integers not exceeding 2n
Case I: If we have 1 in our set,then we are done as gcd(a, 1)= 1
so a and n are relatively prime
Case II:
If 1 is not present in out set we will use pegion hole principle in this, which states that if more than n objects are placed into n boxes then at least one box must contain more than one object or in other form of pegion hole we can say that if the average of n positive numbers is t, then at least one of the numbers is greater than or equal to t.
Furteher at least one of the numbers is kess than or equal to t.
This means that by pegionhole principle we can say that we can create n subsets of co-primes as
{2k-1, 2k} where 1 <= k<= n
difference amongst them is 1, so there GCD is also 1.
they will be co-prime.
Please, please upvote and ask your doubts in the comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.