قانون تقابل درجه دوم

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مانده و نامانده[ویرایش]

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

مثال[ویرایش]

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

چند قضیه مرتبط[ویرایش]

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

1^2, 2^2, 3^2, \cdots, (\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{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}

مثال[ویرایش]

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

محک اویلر[ویرایش]

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

اثبات[ویرایش]

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

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

حال فرض کنید \; g ریشه اولیه \; p باشد، پس \; iای هست که داشته باشیم a \equiv g^i \pmod{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}} \not \equiv 1 \pmod{p} یعنی a^{\frac{p-1}{2}} \equiv -1 \pmod{p}

قانون تقابل درجه دوم[ویرایش]

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

 (\frac{p}{q}) \times (\frac{q}{p})= (-1)^{(\frac{p-1}{2})(\frac{q-1}{2})}

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

منابع[ویرایش]

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