جواب تمرین صفحه ۸۰ ریاضیات گسسته

حل:

می‌دانیم باقی‌مانده‌ی تقسیم هر عدد طبیعی بر \(n\) یکی از اعضای مجموعه‌ی \(R=\{0,1,2,\ldots,n-1\}\) است. این مجموعه \(n\) عضو دارد.

حال \(n+1\) عدد طبیعی دلخواه را کبوترها و باقی‌مانده‌های تقسیم آن‌ها بر \(n\) را لانه‌ها فرض می‌کنیم. تعداد کبوترها \(n+1\) و تعداد لانه‌ها \(n\) است، یعنی \(n+1>n\).

طبق اصل لانه‌کبوتری حداقل در یک لانه دو کبوتر قرار می‌گیرد؛ یعنی حداقل دو عدد از این \(n+1\) عدد، مانند \(a\) و \(b\)، باقی‌مانده‌ی تقسیمشان بر \(n\) یکسان است.

پس \(a\) و \(b\) بر \(n\) باقی‌مانده‌ی یکسان دارند و بنابر تعریف هم‌نهشتی داریم:
\[a \stackrel{n}{\equiv} b\]

یعنی تفاضل آن‌ها، \(a-b\)، بر \(n\) بخش‌پذیر است و حکم ثابت می‌شود. \(\blacksquare\)