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

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

مثال

• ${\displaystyle \;3}$ به پیمانه ${\displaystyle \;13}$ مانده‌است زیرا ${\displaystyle 4^{2}\equiv 3{\pmod {13}}{\mbox{ }}}$
• همه اعداد مربع کامل به پیمانه هر عددی مانده اند.

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

• مانده‌های به پیمانه عدد اول ${\displaystyle \;p}$ دقیقاً اعداد زیر اند

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

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

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

مثال

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

محک اویلر

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

اثبات

طبق قضیه کوچک فرما می‌دانیم برای هر${\displaystyle \;x}$ داریم ${\displaystyle x^{p-1}\equiv 1{\pmod {p}}}$ .پس ${\displaystyle 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{\mbox{ or }}a^{\frac {p-1}{2}}+1\equiv 0{\pmod {p}}}$

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

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

اگر ${\displaystyle \;p}$ و ${\displaystyle \;q}$ دو عدد اول، فرد و متمایز باشند آنگاه داریم:

${\displaystyle {\Biggl (}{\frac {p}{q}}{\Biggr )}\times {\Biggl (}{\frac {q}{p}}{\Biggr )}=(-1)^{({\frac {p-1}{2}})({\frac {q-1}{2}})}}$

دو پرانتز ظاهر شده در توان ${\displaystyle \;-1}$ نماد لژاندر نیستند.

کتاب نظریه اعداد، مریم میرزاخانی، رؤیا بهشتی زواره، انتشارات فاطمی