இருபடிய எச்சம்

கணிதத்தில் எண் கோட்பாட்டில் இருபடிய எச்சம் (Quadratic Residue) என்ற கருத்து ஒரு அடிப்படைக் கருத்து. ஓர் முழுஎண்ணானது சமானம் மாடுலோ கருத்துருவின்கீழ் மற்றொரு முழுஎண்ணின் முழுவர்க்கத்திற்குச் சமானமாக இருந்தால் அது இருபடிய எச்சம் எனப்படும்.

சமானம் மாடுலோ n இருபடிய எச்சம் முழுஎண் q எனில் பின்வரும் கூற்றை நிறைவு செய்யும் வகையில் x என்ற முழுஎண்ணைக் காணலாம்:

${\displaystyle x^{2}\equiv q{\pmod {n}}.}$ (0 < x < n)

இரண்டு இருபடிய எச்சங்களின் பெருக்குத்தொகையும் ஒரு இருபடிய எச்சமாக இருக்கும்.

எடுத்துக்காட்டாக,

${\displaystyle 3^{2}\equiv 2(mod7)}$ என்றால், மாடுலோ 7 இனுடைய ஒரு இருபடிய எச்சம் 2 என்று சொல்லப்படும். மாடுலோ எண் கணிதத்தில் இருபடிய எச்சங்கள் வர்க்க மூலம் உள்ள எண்களாக இருக்கும். இங்கு மாடுலோ 7 என்ற மாடுலோ எண் கணிதத்தில் 2 இன் வர்க்கமூலம் 3.

வரலாறு

பெர்மா, ஆய்லர், லாக்ராஞ்சி, லெஜாண்டர் மற்றும் பல 17 ஆம், 18 ஆம் நூற்றாண்டின் கோட்பாட்டாளர்கள் இருபடிய எச்சம் குறித்த பல தேற்றங்கள், அவற்றின் நிறுவல்கள் மற்றும் அனுமானங்களைக் கண்டறிந்திருந்தாலும்^[1][2] ஜெர்மானிய கணித வல்லுனர் காஸினால் அவர் அறிமுகப்படுத்திய மாடுலோ எண் கணிதம் மூலம் விவரமாக ஆய்வு செய்யப்பட்டது. இருபடிய எச்சம் குறித்த முறைப்படுத்தப்பட்ட அணுகுமுறை முதன்முதலில் கணிதவியலாளர் காசின் புத்தகத்தில் (§ IV Disquisitiones Arithmeticae (1801)) காணப்பட்டது. "இருபடிய எச்சம் (quadratic residue)" என்ற சொல் இப்புத்தகத்தில் பிரிவு 95 இல் தரப்பட்டுள்ளது. சிலசமயங்களில் ’இருபடிய’ என்ற அடைமொழியின்றி ’எச்சம்’ என்று மட்டும்கூட குறிப்பிடப்படலாம்.

முறையான அறிமுகம்

ஒரு பகா எண் ${\displaystyle p}$ ஐயும், ஒரு முழு எண் ${\displaystyle a}$ ஐயும் எடுத்துக்கொள்வோம். ஏதாவது ஒரு முழு எண் ${\displaystyle x}$ க்கு

${\displaystyle x^{2}\equiv a(modp)}$ (இதையே ${\displaystyle a\equiv x^{2}(modp)}$ என்றும் எழுதலாம்)

என்பது உண்மையானால், மாடுலோ ${\displaystyle p}$ க்கு ${\displaystyle a}$ ஒரு இருபடிய எச்சம் என்று கூறப்படும். இதையே ${\displaystyle a}$ என்ற எண் ${\displaystyle p}$ இனுடைய இருபடிய எச்சம் என்றும் சொல்வதுண்டு.

இக்கட்டுரை முழுவதும் மாடுலோ எண்கணிதத்தைப்பற்றியே இருப்பதால் '${\displaystyle \equiv }$' இருக்கவேண்டிய இடத்தில் '=' குறியையே பயன்படுத்துவோம்.

எந்த முழுஎண் ${\displaystyle x}$ க்கும்

${\displaystyle x^{2}\neq a(modp)}$ (இதையே ${\displaystyle a\neq x^{2}(modp)}$ என்றும் எழுதலாம்)

என்பது உண்மையானால், மாடுலோ ${\displaystyle p}$ க்கு ${\displaystyle a}$ ஒரு இருபடிய எச்சமல்லாதது (quadratic non-residue) என்று கூறப்படும். இதையே ${\displaystyle a}$ என்ற எண் ${\displaystyle p}$ இனுடைய இருபடிய எச்சமல்லாதது என்றும் சொல்வதுண்டு.

குறியீடு

இருபடிய எச்சமாக இருப்பதைக் குறிக்க R ம் இல்லாததைக் குறிக்க N ம் காசால் பயன்படுத்தப்பட்டது^[3]

p இன் இருபடிய எச்சம் q என்பதன் குறியீடு: ${\displaystyle _{q}R_{p}}$

p இன் இருபடிய எச்சம் q இல்லையென்பதின் குறியீடு: ${\displaystyle _{q}N_{p}}$

${\displaystyle 11=2^{2}(mod7)}$ ${\displaystyle \therefore }$ 11, 7இனுடைய இருபடிய எச்சம். அதாவது குறியீட்டில் ${\displaystyle _{11}R_{7}}$

ஆனால் 7, மாடுலோ 11 க்கு ஒரு இருபடிய எச்சமல்லாதது. குறியீட்டில் ${\displaystyle _{7}R_{11}}$

11 இன் எல்லா எச்சங்களையும் வர்க்கப்படுத்தி பட்டியலிட்டால் இதைச் சரிபார்க்கலாம்.

${\displaystyle 1^{2}=1(mod11)}$

${\displaystyle 2^{2}=4(mod11)}$

${\displaystyle 3^{2}=9(mod11)}$

${\displaystyle 4^{2}=5(mod11)}$

${\displaystyle 5^{2}=3(mod11)}$

${\displaystyle 6^{2}=3(mod11)}$

${\displaystyle 7^{2}=5(mod11)}$

${\displaystyle 8^{2}=9(mod11)}$

${\displaystyle 9^{2}=4(mod11)}$

${\displaystyle 10^{2}=1(mod11)}$${\displaystyle \therefore }$ 1,3,4,5,9 இவ்வைந்து எண்கள்தான் 11 இன் இருபடிய எச்சங்கள். 2, 6, 7, 8, 10 இவ்வைந்தும் இருபடிய எச்சமல்லாதவை.

எடுத்துக்காட்டுகள்

a² ≡ (n − a)² (மாடுலோ n) என்பதால் 1 முதல் n − 1 வரையிலான முழு எண்களை வர்க்கப்படுத்தி, மாடுலோ n இன் இருபடிய எச்சங்களைக் காணலாம்.

• மாடுலோ 4

${\displaystyle 1^{2}\equiv 1{\pmod {4}}}$

${\displaystyle 2^{2}\equiv 0{\pmod {4}}}$

${\displaystyle 3^{2}\equiv 1{\pmod {4}}}$

மாடுலோ 4 இன் இருபடிய எச்சம்: 1

• மாடுலோ 5

${\displaystyle 1^{2}\equiv 1{\pmod {5}}}$

${\displaystyle 2^{2}\equiv 4{\pmod {5}}}$

${\displaystyle 3^{2}\equiv 4{\pmod {5}}}$

${\displaystyle 4^{2}\equiv 1{\pmod {5}}}$

மாடுலோ 5 இன் இருபடிய எச்சங்கள்: 1, 4

• மாடுலோ 10:

${\displaystyle 1^{2}\equiv 1{\pmod {10}}}$

${\displaystyle 2^{2}\equiv 4{\pmod {10}}}$

${\displaystyle 3^{2}\equiv 9{\pmod {10}}}$

${\displaystyle 4^{2}\equiv 6{\pmod {10}}}$

${\displaystyle 5^{2}\equiv 5{\pmod {10}}}$

${\displaystyle 6^{2}\equiv 6{\pmod {10}}}$

${\displaystyle 7^{2}\equiv 9{\pmod {10}}}$

${\displaystyle 8^{2}\equiv 4{\pmod {10}}}$

${\displaystyle 9^{2}\equiv 1{\pmod {10}}}$

மாடுலோ 10 இன் இருபடிய எச்சங்கள்: 1, 4, 5, 6, 9

எண்ணிக்கை

மாடுலோ n இன் இருபடிய எச்சங்களின் எண்ணிக்கையானது,

• n இரட்டையெண்ணாக இருக்கும்போது n/2 + 1 க்கு மிகாமலும்
• n ஒற்றையெண்ணாக இருக்கும்போது (n + 1)/2 க்கு மிகாமலும் இருக்கும்.^[4]

மேலேதரப்பட்டுள்ள எடுத்துக்காட்டுகளின்படி:

• மாடுலோ 4 இன் எச்சங்களின் எண்ணிக்கை 1. (4/2+1 = 3ஐ விடக் குறைந்த எண்ணிக்கை)
• மாடுலோ 5 இன் எச்சங்களின் எண்ணிக்கை 2 ((5+1)/2+1=4ஐ விடக் குறைந்த எண்ணிக்கை)
• மாடுலோ 10 இன் எச்சங்களின் எண்ணிக்கை 5 (10/2+1=6ஐ விடக் குறைந்த எண்ணிக்கை)