Question

Consider the integers 429, 1330, 414, and 46. Using the pigeonhole principle, show that there exists an integer x such that ? =429?+414 and ?=1330?+46 for some integers p and q.

Answer 1

are and when and Note that 429 = 3 X 110 13. and 1330 = 275 X 7 X 19. Thus, 429 and 1330 relatively prime. Consider the set $={414+ K429 : 0 5k<1330} . Now, we claim that if K, 7 kz be such that ki, K₂ € {0, 1,..., 1330-13, then 414 + k,,429 414+ K₂429 leave distinct remainders Livided by 1330 Let K, < K₂ (without loss of generality) if possible both of 414+ 429K, , 414+k₂429 remainder œ when divided by 1330. by division algorithm there exists a, bf 2 such that, 414+ 429 K, = 1330.ata 414 + 429 K2 1330 b ta subtracting we're 425 (K, -K2) 1330 (935) → 1330. | 429 CK, -kz) => 1330 | K, -Kz → 1330 | k₂-ki. (1330 X 429) which is a contradiction because Hence OSK,<k< 1330 claim follows. leave same Thus own

Next note that Ş has of which leaves distinct 1330 elements each remainders when dinted

set of by 1330. Hence the set of remaindersti a Cardinality 1330. Now, if 46 doesn't appear remainder, then RC {0, 1,. --, 132571463 · But pigeonhole principre affirms that this is not possible. because of Cardinality 1330 Can't be a subset of a set of Cardinality 1329. Thus, OSR< 1328 such that, 414 + 429 p et leaves remainder 46 46 when divided by 1330 → 414+ 429 P 1330 q +46 for some LG ZZ Proved). a set