بخش‌پذیری در اعداد صحیح

می‌گوییم a بر b بخش‌پذیر است، یا b عدد a را می‌شمارد، وقتی عدد صحیحی مثل q باشد که a = bq. این را b|a می‌نویسیم. مثلاً ۷|۲۱ چون ۲۱ = ۷×۳.

اگر a بر b بخش‌پذیر نباشد، باقی‌مانده داریم. برای هر دو عدد صحیح a و ⁦b (b ≠ 0)⁩ فقط یک خارج‌قسمت q و یک باقی‌مانده r پیدا می‌شود که a = bq + r و r از صفر کوچک‌تر نیست و از b هم کوچک‌تر است. این الگوریتم تقسیم است.

اگر b عدد a و عدد c را بشمارد، هر عددی به شکل ax + cy را هم می‌شمارد (x و y عددهای صحیح دلخواه‌اند). پس b ترکیب خطی آن دو را هم می‌شمارد.

با برگشت از مرحله‌های روش اقلیدس می‌توان بزرگ‌ترین قاسم مشترک دو عدد را به شکل ax + by نوشت. برعکسش هم مهم است: معادلهٔ ax + by = c در اعداد صحیح فقط وقتی جواب دارد که بزرگ‌ترین قاسم مشترک عددهای a و b عدد c را بشمارد.

در هر مرحله، روی برگهٔ تقسیم یا جعبهٔ پاسخ کار کن؛ اگر گیر کردی، راهنمایی را بخوان.