آشنایی با نظریۀ اعداد

پاسخنامه‌ی تحلیلی

بر اساس قضیه حذف در هم‌نهشتی، اگر $ac \equiv bc \pmod{m}$ و $d = \gcd(c, m)$، آنگاه $a \equiv b \pmod{m/d}$. بنابراین گزینه «$a \equiv b \pmod{m/d}$» درست است. تلهٔ تستی: باید توجه شود که $c$ خودش ممکن است هم‌ارزِ $0$ به پیمانه‌ای غیرِ‌بدیهی باشد؛ پیمانهٔ نتیجه همیشه $m/d$ است، نه خودِ $m$ — استفادهٔ نادرست از $m$ به‌جایِ $m/d$، رایج‌ترین خطاست.

پاسخنامه‌ی تحلیلی

«$x=2+5k,\ y=1-2k$» درست است. گام به گام: $d=\gcd(6,15)=3$ و چون $3\mid 27$، معادله جواب صحیح دارد. با تقسیم بر $3$: $2x+5y=9$. یک جوابِ خاص $(x_0,y_0)=(2,1)$ است، زیرا $2(2)+5(1)=9$. جوابِ عمومی طبقِ فرمولِ $x=x_0+\frac{b}{d}k$ و $y=y_0-\frac{a}{d}k$ می‌شود $x=2+\frac{15}{3}k=2+5k$ و $y=1-\frac{6}{3}k=1-2k$. وارسیِ مستقل با جای‌گذاری: $6(2+5k)+15(1-2k)=12+30k+15-30k=27$، مستقل از $k$ برقرار است. ردِّ گزینه‌های دیگر: «$x=2+2k,\ y=1-5k$» ضرایبِ $k$ را جابه‌جا کرده؛ جای‌گذاری می‌دهد $6(2+2k)+15(1-5k)=27-63k$ که فقط برایِ $k=0$ درست است، پس خانوادهٔ جواب نیست. «$x=3-5k,\ y=1+2k$» و «$x=3+5k,\ y=1-2k$» هر دو با $k=0$ به $(3,1)$ می‌رسند و $6(3)+15(1)=33\neq 27$، پس اصلاً از یک جوابِ خاصِ درست شروع نشده‌اند. تلهٔ تستی: هر جوابِ عمومی باید در دو چیز آزموده شود — نخست اینکه با $k=0$ یک جوابِ واقعی بدهد، و دوم اینکه ضریبِ $k$ در $x$ برابرِ $b/d$ و در $y$ برابرِ $-a/d$ باشد؛ خانواده‌ای که فقط شرطِ اول را دارد (مثلِ گزینهٔ ضرایب‌جابه‌جا) در همان گامِ دوم رد می‌شود.

پاسخنامه‌ی تحلیلی

وارون ضربی عدد $a$ به پیمانه $m$ عددی مانند $x$ است که $ax \equiv 1 \pmod{m}$. با بررسی، $13 \times 20 = 260$ و $260 \div 37$ باقیمانده $1$ می‌دهد. بنابراین $20$ وارون ضربی $13$ به پیمانه $37$ است. تلهٔ تستی: برایِ یافتنِ وارونِ ضربی، الگوریتمِ اقلیدسِ توسعه‌یافته باید تا انتها دنبال شود؛ توقف در یک گامِ میانی و گزارشِ یک مقدارِ نادرست، رایج‌ترین خطاست. می‌توان نتیجه را با ضربِ مستقیم ($13\times20=260=7\times37+1$) تأیید کرد.

پاسخنامه‌ی تحلیلی

«$0$» درست است زیرا $4^{x}$ برای $x\geq 1$ همواره بر $4$ بخش‌پذیر است در نتیجه به پیمانه $12$ یا $0$ یا $4$ یا $8$ است، اما برای $x=0$ داریم $4^{0}=1$ و $1\not\equiv 8 \pmod{12}$ و $12 \nmid (4^{x}-8)$ برای هیچ $x$ طبیعی. گزینه‌های دیگر ($1$ و $2$ و $3$) غلطند زیرا با بررسی $x=1,2,3,4,5$ هیچ‌کدام در هم‌نهشتی داده‌شده صدق نمی‌کنند. تلهٔ تستی: باید تک‌تکِ مقادیرِ $x$ در بازهٔ داده‌شده مستقیماً آزموده شوند، نه اینکه با یک قاعدهٔ کلیِ نادرست (مثلِ فرضِ وجودِ همیشگیِ جواب) نتیجه‌گیری شود — وقتی پایه و پیمانه هم‌اول نیستند، رفتارِ توان‌ها می‌تواند کاملاً غیرِمنتظره باشد.

پاسخنامه‌ی تحلیلی

«$2$» درست است زیرا هر جمله $a^{a}$ را به پیمانه $5$ محاسبه می‌کنیم. با استفاده از قضیه فرما یا الگوی توان: $1^{1}\equiv1$, $2^{2}\equiv4$, $3^{3}\equiv2$, $4^{4}\equiv1$, $5^{5}\equiv0$, $6^{6}\equiv1$, $7^{7}\equiv3$, $8^{8}\equiv1$, $9^{9}\equiv4$, $10^{10}\equiv0$. مجموع آنها $1+4+2+1+0+1+3+1+4+0=17\equiv2 \pmod{5}$. گزینه‌های $0$, $3$, $4$ غلطند زیرا مجموع واقعی $17$ با هیچکدام هم‌نهشت نیست. تلهٔ تستی: باید باقیماندهٔ هر جملهٔ $k^k$ جداگانه محاسبه و سپس جمع گرفته شود؛ برایِ $k\geq5$، چون $k^k$ خودش بر $5$ اثر می‌گذارد، نمی‌توان الگویِ ساده‌ای برایِ همهٔ جمله‌ها به‌کار برد — هر جمله باید مستقل بررسی شود.

پاسخنامه‌ی تحلیلی

«$59$» درست است. گام به گام: هر سه هم‌نهشتی را می‌توان به شکلِ یکنواخت نوشت: $x\equiv 3\equiv -1\pmod 4$، $x\equiv 4\equiv -1\pmod 5$ و $x\equiv 5\equiv -1\pmod 6$. پس $x+1$ هم‌زمان بر $4$ و $5$ و $6$ بخش‌پذیر است، یعنی $\mathrm{lcm}(4,5,6)=60$ عددِ $x+1$ را می‌شمارد. بنابراین $x\equiv -1\equiv 59\pmod{60}$ و کوچک‌ترین مقدارِ طبیعی $x=59$ است. وارسیِ مستقل با جای‌گذاریِ مستقیم: $59=4\times14+3$ ✓، $59=5\times11+4$ ✓، $59=6\times9+5$ ✓. ردِّ گزینه‌های دیگر: «$29$» چون $29=4\times7+1$ باقیماندهٔ $1$ بر $4$ می‌دهد نه $3$. «$89$» چون $89=4\times22+1$، باز هم باقیماندهٔ $1$ بر $4$. «$119$» در هر سه هم‌نهشتی صدق می‌کند ($119=60+59$)، اما پرسش کوچک‌ترین عدد را می‌خواهد و $59<119$. تلهٔ تستی: پیمانه‌های $4$ و $5$ و $6$ دوبه‌دو نسبت به هم اول نیستند ($\gcd(4,6)=2$)، پس نمی‌توان کورکورانه حاصل‌ضربِ $4\times5\times6=120$ را دورهٔ تناوب گرفت؛ دورهٔ درست $\mathrm{lcm}=60$ است و همین باعث می‌شود گزینهٔ $119$ هم جواب باشد ولی کوچک‌ترین نباشد.

پاسخنامه‌ی تحلیلی

با استفاده از قضیه فرما، $2^{12} \equiv 1 \pmod{13}$. داریم $2024 = 12 \times 168 + 8$، بنابراین $2^{2024} \equiv 2^8 = 256 \equiv 256 - 13 \times 19 = 256 - 247 = 9 \pmod{13}$. تلهٔ تستی: دورهٔ تناوبِ باقیماندهٔ توان‌هایِ $2$ به پیمانهٔ $13$ برابرِ $12$ است؛ خطایِ رایج این است که یا این دوره اشتباه محاسبه شود، یا وقتی باقیماندهٔ توان بر دوره صفر می‌شود، به‌جایِ **آخرین** عضوِ دوره، به اشتباه عددِ $1$ یا اولین عضو گزارش شود.

پاسخنامه‌ی تحلیلی

«$x=-1,\ y=1$» درست است. گام به گام: نخست وجودِ جواب را می‌سنجیم: $d=\gcd(4,10)=2$ و $2\mid 6$، پس معادله جوابِ صحیح دارد. با تقسیم بر $2$: $2x+5y=3$. جای‌گذاریِ گزینهٔ «$x=-1,\ y=1$»: $4(-1)+10(1)=-4+10=6$ ✓. وارسیِ مستقل از راهِ ساختارِ جوابِ عمومی: از $(x_0,y_0)=(-1,1)$ داریم $x=-1+5k$ و $y=1-2k$؛ برای $k=1$ به $(4,-1)$ و برای $k=-1$ به $(-6,3)$ می‌رسیم — یعنی جواب‌های صحیح فقط روی این خانواده‌اند. ردِّ گزینه‌های دیگر: $4(-6)+10(2)=-24+20=-4\neq 6$؛ $4(5)+10(-1)=20-10=10\neq 6$؛ $4(8)+10(-3)=32-30=2\neq 6$. هیچ‌کدام روی خانوادهٔ $(-1+5k,\ 1-2k)$ نیستند. تلهٔ تستی: چون هر دو ضریبِ $4$ و $10$ زوج‌اند، سمتِ چپ همیشه زوج است؛ پس هر گزینه‌ای که عددی فرد بدهد بی‌درنگ رد می‌شود، اما زوج‌بودنِ حاصل به‌تنهایی کافی نیست — مقدارِ دقیقِ $6$ باید به دست بیاید (گزینه‌های $-4$ و $10$ و $2$ همگی زوج‌اند و با این حال نادرست‌اند).

پاسخنامه‌ی تحلیلی

«$3$» درست است. با حل $3x \equiv 47 \pmod{5}$ داریم $3x \equiv 2 \pmod{5}$ که $x \equiv 4 \pmod{5}$، پس $x = 5k + 4$. با جایگذاری در معادله: $3(5k+4) + 5y = 47 \implies 15k + 12 + 5y = 47 \implies 5y = 35 - 15k \implies y = 7 - 3k$. با شرط $x > 0$ و $y > 0$، داریم $5k + 4 > 0 \implies k \geq 0$ و $7 - 3k > 0 \implies k \leq 2$، یعنی $k = 0, 1, 2$. بنابراین ۳ جواب مثبت وجود دارد. تلهٔ تستی: پیش از هر محاسبه‌ای باید بررسی شود که $\gcd(3,5)=1$ بر $47$ بخش‌پذیر است (که اینجا برقرار است، پس جواب وجود دارد)؛ در شمارشِ جواب‌هایِ طبیعی/نامنفی، هر دو کرانِ پایین و بالایِ پارامتر باید هم‌زمان اعمال شوند، نه فقط یکی.

پاسخنامه‌ی تحلیلی

«$53$» درست است. گام به گام: از $n\equiv 2\pmod 3$ می‌نویسیم $n=3k+2$. در $n\equiv 3\pmod 5$: $3k+2\equiv 3\pmod 5\Rightarrow 3k\equiv 1\pmod 5$؛ وارونِ $3$ به پیمانهٔ $5$ برابرِ $2$ است ($3\times2=6\equiv1$)، پس $k\equiv 2\pmod 5$ و $k=5t+2$، یعنی $n=15t+8$. حال در $n\equiv 1\pmod 4$: $15t+8\equiv 1\pmod 4\Rightarrow 3t\equiv 1\pmod 4$؛ وارونِ $3$ به پیمانهٔ $4$ برابرِ $3$ است، پس $t\equiv 3\pmod 4$ و $t=4s+3$، یعنی $n=60s+53$. کوچک‌ترین مقدارِ طبیعی با $s=0$ برابرِ $53$ است. وارسیِ مستقل با جای‌گذاری: $53=3\times17+2$ ✓، $53=5\times10+3$ ✓، $53=4\times13+1$ ✓. ردِّ گزینه‌های دیگر: «$11$» دو هم‌نهشتیِ اول را نقض می‌کند از جهتِ پیمانهٔ $5$ ($11=5\times2+1$، باقیمانده $1$ نه $3$). «$23$» در دو شرطِ اول صدق می‌کند ($23=3\times7+2$ و $23=5\times4+3$) اما در شرطِ سوم می‌شکند: $23=4\times5+3$، باقیمانده $3$ است نه $1$. «$38$» نیز دو شرطِ اول را دارد ($38=3\times12+2$، $38=5\times7+3$) ولی $38=4\times9+2$ باقیماندهٔ $2$ می‌دهد نه $1$. تلهٔ تستی: دو گزینهٔ $23$ و $38$ دقیقاً برای همین ساخته شده‌اند که با ارضایِ دو هم‌نهشتی از سه‌تا فریب بدهند؛ جوابِ نهایی باید در **هر سه** هم‌نهشتی جداگانه آزموده شود، نه فقط در آن‌هایی که اول بررسی شده‌اند.