قانون تقابل مربعی

قانون تقابل مربعی الگو:به انگلیسی، قضیه‌ای است قدرتمند در شاخه نظریه اعداد از ریاضیات. با وجود آنکه قوانینی مشابه برای درجه سوم و بالاتر ثابت شده‌است، اما همچنان این قضیه، بسیار پرکاربرد و قدرتمند ظاهر می‌شود و استفاده از آن متوقف نگشته‌است. برای بیان این قضیه ابتدا دو تعریف ارائه می‌دهیم.

مانده و نامانده

$p$ عددی اول و فرد و $a$ عددی صحیح و نسبت به $p$ اول است. اگر معادله همنهشتی $x^{2} \equiv a (\mod p)$ جواب داشته باشد، آنگاه عدد $a$ را به پیمانه $p$ مانده و در غیر این صورت نامانده می‌گوییم.

مثال

$3$ به پیمانه $13$ مانده‌است زیرا $4^{2} \equiv 3 (\mod 13)$
همه اعداد مربع کامل به پیمانه هر عددی مانده اند.

چند قضیه مرتبط

مانده‌های به پیمانه عدد اول $p$ دقیقاً اعداد زیر اند

$1^{2}, 2^{2}, 3^{2}, \dots, (\frac{p - 1}{2})^{2}$

برای هر $p$ اول، دقیقاً $\frac{p - 1}{2}$ مانده متمایز به هنگ $p$ و به همین تعداد نامانده وجود دارد.

نماد لژاندر

اگر $p$ عددی اول و فرد و $a$ عددی صحیح باشند که $(a, p) = 1$ تابع لژاندر با نماد $(\frac{a}{p})$ برابر است با $1$ اگر $a$ در مبنای $p$ مانده باشد و در غیر این صورت برابر است با $- 1$ . به عبارت دیگر: $(\frac{a}{p}) = {\begin{matrix} + 1 if x^{2} \equiv a (\mod p) has a root \\ - 1 if x^{2} \equiv a (\mod p) has no root \end{matrix}$

مثال

در همان مثال قبل می‌توان نوشت $(\frac{3}{13}) = 1$

محک اویلر

اگر $p$ عددی اول و فرد و $a$ عددی صحیح و نسبت به آن اول باشد، آنگاه داریم $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (\mod p)$

اثبات

طبق قضیه کوچک فرما می‌دانیم برای هر $x$ داریم $x^{p - 1} \equiv 1 (\mod p)$ . پس $0 \equiv a^{p - 1} - 1 = (a^{\frac{p - 1}{2}} + 1) (a^{\frac{p - 1}{2}} - 1) \Rightarrow a^{\frac{p - 1}{2}} - 1 \equiv 0 or a^{\frac{p - 1}{2}} + 1 \equiv 0 (\mod p)$

اگر $a$ مانده باشد، برای یک $x$ ایی داریم $a \equiv x^{2} (\mod p)$ و این نتیجه می‌دهد $a^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1 (\mod p)$

حال فرض کنید $g$ ریشه اولیه $p$ باشد، پس $i$ ای هست که داشته باشیم $a \equiv g^{i} (\mod p)$ . پس $a^{\frac{p - 1}{2}} \equiv g^{\frac{i \times (p - 1)}{2}}$ . اگر $a$ نامانده باشد، آنگاه حتماً $i$ فرد است و در نتیجه $\frac{i \times (p - 1)}{2}$ بر $p - 1$ بخش پذیر نیست و این به دلیل ریشه اول بودن $g$ نتیجه می‌دهد $g^{\frac{i \times (p - 1)}{2}} \equiv̸ 1 (\mod p)$ یعنی $a^{\frac{p - 1}{2}} \equiv - 1 (\mod p)$