Question

Using pigeonhole principle prove that in any group of 5 integers, not necessarily consecutive, there are...

Using pigeonhole principle prove that in any group of 5 integers, not necessarily consecutive, there are 2 with same remainder when divided by 9

Homework Answers

Answer #1

No, it cannot happen at all.

Since the numbers are divided by 9 and it has more possible number of remainders than 5.

There are nine possible remainders when an integer is divided by 9: 0, 1, 2, 3, 4, 5, 6, 7 or 8 (these are pigeonholes). But when a group of 5 integers is divided by 9 (no doubt that the remainder will be from the above numbers) but not necessarily there are 2 with same remainder as .

it can happen when the group of 5 integers, not necessarily consecutive, when divided by any number less than 5 obviously greater than 1.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Discrete Math: 8) Prove that among any set of seven (not necessarily consecutive) integers, there are...
Discrete Math: 8) Prove that among any set of seven (not necessarily consecutive) integers, there are at least two with the same remainder when divided by 6.
Let n ≥ 1 be an integer. Use the Pigeonhole Principle to prove that in any...
Let n ≥ 1 be an integer. Use the Pigeonhole Principle to prove that in any set of n + 1 integers from {1, 2, . . . , 2n}, there are two elements that are consecutive (i.e., differ by one).
Prove deductively that for any three consecutive odd integers, one of them is divisible by 3
Prove deductively that for any three consecutive odd integers, one of them is divisible by 3
Prove that the sum of 2 consecutive integers is positive
Prove that the sum of 2 consecutive integers is positive
Using the pigeonhole theorem prove that an algorithm cannot losslessly compress any 1024-bit binary string so...
Using the pigeonhole theorem prove that an algorithm cannot losslessly compress any 1024-bit binary string so that it's not more than 1023 bits.
LetG be a group (not necessarily an Abelian group) of order 425. Prove that G must...
LetG be a group (not necessarily an Abelian group) of order 425. Prove that G must have an element of order 5.
Let G be a group (not necessarily an Abelian group) of order 425. Prove that G...
Let G be a group (not necessarily an Abelian group) of order 425. Prove that G must have an element of order 5. Note, Sylow Theorem is above us so we can't use it. We're up to Finite Orders. Thank you.
Cubes can be written as sums of consecutive odd integers Express 5^3 in a similar manner...
Cubes can be written as sums of consecutive odd integers Express 5^3 in a similar manner as demonstrated by the pattern in the figure. State and prove a formula for n^3 Illustrate your formula geometrically with cubic blocks
1. Prove that an integer a is divisible by 5 if and only if a2 is...
1. Prove that an integer a is divisible by 5 if and only if a2 is divisible by 5. 2. Deduce that 98765432 is not a perfect square. Hint: You can use any theorem/proposition or whatever was proved in class. 3. Prove that for all integers n,a,b and c, if n | (a−b) and n | (b−c) then n | (a−c). 4. Prove that for any two consecutive integers, n and n + 1 we have that gcd(n,n + 1)...
3. a) For any group G and any a∈G, prove that given any k∈Z+, C(a) ⊆...
3. a) For any group G and any a∈G, prove that given any k∈Z+, C(a) ⊆ C(ak). (HINT: You are being asked to show that C(a) is a subset of C(ak). You can prove this by proving that if x ∈ C(a), then x must also be an element of C(ak) for any positive integer k.) b) Is it necessarily true that C(a) = C(ak) for any k ∈ Z+? Either prove or disprove this claim.