ഓയ്ലറുടെ ടോഷ്യന്റ് ഫലനം

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Euler%27s_totient_function

ടോഷ്യന്റ് ഫലനത്തിന്റെ ആദ്യത്തെ നൂറ് വിലകൾ കാണിക്കുന്ന ഗ്രാഫ്

ഒരു ധനപൂർണ്ണസംഖ്യയെക്കാൾ വലുതല്ലാത്തതും അതിനോട് സഹ-അഭാജ്യവുമായ (coprime) ധനപൂർണ്ണസംഖ്യകളുടെ എണ്ണമാണ്‌ സംഖ്യാസിദ്ധാന്തത്തിൽ ഓയ്ലറുടെ ടോഷ്യന്റ് ഫലനം (Euler's totient function) എന്നറിയപ്പെടുന്നത്. ഇതിനെക്കുറിച്ച് പഠിച്ച സ്വിസ്സ് ഗണിതശാസ്ത്രജ്ഞനായ ലെയൻഹാർട് ഓയ്ലറുടെ പേരിലാണ്‌ ഫലനം അറിയപ്പെടുന്നത്. ടോഷ്യന്റ് ഫലനം, ഓയ്ലറുടെ ഫൈ ഫലനം, ഫൈ ഫലനം എന്നീ പേരുകളിലും ഇത് അറിയപ്പെടുന്നു. $n$ എന്ന സംഖ്യയുടെ ടോഷ്യന്റ് ഫലനം $\varphi \left(n\right)$ എന്നാണ്‌ എഴുതുക.

ഒരു സംഖ്യയെക്കാൾ വലുതല്ലാത്തതും അതിനോട് സഹഅഭാജ്യവുമായ സംഖ്യകളെ ടോട്ടേറ്റീവുകൾ എന്നാണ്‌ വിളിക്കുക. ഒരു ധനപൂർണ്ണസംഖ്യയുടെ ടോട്ടേറ്റീവുകളുടെ എണ്ണമാണ്‌ അതിന്റെ ടോഷ്യന്റ് ഫലനം.

ഉദാഹരണം

9 എന്ന സംഖ്യയുടെ ടോഷ്യന്റ് ഫലനം കാണുന്നതെങ്ങനെയെന്ന് നോക്കാം. 9-നെക്കാൾ വലുതല്ലാത്ത ധനപൂർണ്ണസംഖ്യകൾ 1,2,3,4,5,6,7,8,9 ആണ്‌. ഇവയിൽ 1,2,4,5,7,8 എന്നിവ 9-നോട് സഹ‌അഭാജ്യമാണ്‌ - അതായത്, 6 സംഖ്യകൾ ഇങ്ങനെയുണ്ട്.

അതിനാൽ $\varphi \left(9\right)=6$

$\varphi \left(1\right)=1$ ആണ്‌.

ബന്ധപ്പെട്ട ഫലനങ്ങളും സംഖ്യകളും

• ഒരു സംഖ്യയുടെയും ടോഷ്യന്റ് ഫലനത്തിന്റെ വിലയായിവരാത്ത ഇരട്ടസംഖ്യകളെ നോൺടോഷ്യന്റ് (Nontotient) എന്നു വിളിക്കുന്നു. ഉദാഹരണം : 14, 26, 34, 38, 50

• ഒരു ധനപൂർണ്ണസംഖ്യയെക്കാൾ വലുതല്ലാത്തതും അതിനോട് സഹഅഭാജ്യമല്ലാത്തതുമായ ധനപൂർണ്ണസംഖ്യകളുടെ എണ്ണത്തെ കോടോഷ്യന്റ് ഫലനം എന്നു വിളിക്കുന്നു. $n$ എന്ന സംഖ്യയുടെ കോടോഷ്യന്റ് ഫലനം $n-\varphi \left(n\right)$ ആണ്‌. ഉദാഹരണത്തിൽ 9-ന്റെ കോടോഷ്യന്റ് ഫലനം 3 ആണ്‌.

• ഒരു സംഖ്യയുടെയും കോടോഷ്യന്റ് ഫലനത്തിന്റെ വിലയായി വരാത്ത ധനപൂർണ്ണസംഖ്യകൾ നോൺകോടോഷ്യന്റ് (Noncototient) എന്നറിയപ്പെടുന്നു. ഉദാഹരണം : 10, 26, 30, 34, 52

• 1 മുതൽ n വരെയുള്ള സംഖ്യകളുടെ ടോഷ്യന്റ് ഫലനങ്ങളുടെ തുക n-ന്റെ ടോഷ്യന്റ് സമ്മേറ്ററി ഫലനം എന്നറിയപ്പെടുന്നു. $\Phi (n)$ ഉപയോഗിച്ചാണ്‌ ഇതിനെ സൂചിപ്പിക്കുന്നത്.

• ടോഷ്യന്റ് ഫലനത്തിന്റെ വില m ആയിട്ടുള്ള സംഖ്യകളുടെ എണ്ണം m-ന്റെ ടോഷ്യന്റ് വാലൻസ് ഫലനം എന്നറിയപ്പെടുന്നു. മൾട്ടിപ്ലിസിറ്റി എന്നും ഇതിന്‌ പേരുണ്ട്. $N_{\varphi \left(n\right)}$ ആണ്‌ ഇതിനെ സൂചിപ്പിക്കാൻ ഉപയോഗിക്കുന്നത്.

• ഓയ്ലറുടെ ടോഷ്യന്റ് ഫലനത്തിനെ k അംഗങ്ങളെ ഉൾക്കൊള്ളിച്ചുകൊണ്ടുള്ള സാമാന്യവത്കരണം നടത്തിയാൽ ലഭിക്കുന്ന ഫലനം ജോർഡാന്റെ ടോഷ്യന്റ് ഫലനം എന്നറിയപ്പെടുന്നു.

കണ്ടെത്തുന്ന വിധം

• $p$ ഒരു അഭാജ്യസംഖ്യയാണെങ്കിൽ $\varphi \left(p^{k}\right)=\left(p-1\right)p^{k-1}$
• $m,n$ എന്നിവ സഹ‌അഭാജ്യസംഖ്യകളാണെങ്കിൽ $\varphi \left(mn\right)=\varphi \left(m\right)\varphi \left(n\right)$

ടോഷ്യന്റ് ഫലനത്തിന്റെ ഈ രണ്ട് പ്രത്യേകതകൾ ഉപയോഗിച്ച് ഏതൊരു സംഖ്യയുടെയും ടോഷ്യന്റ് ഫലനം കണ്ടെത്താം. ഇതിനുള്ള വഴി:

$n$ ഒരു ധനപൂർണ്ണസംഖ്യയാണെങ്കിൽ അതിനെ $p_{1}^{k_{1}}p_{2}^{k_{2}}\ldots p_{r}^{k_{r}}$ എന്ന രിതിയിൽ എഴുതാം. ഇവിടെ $p_{i}$ കളെല്ലാം വ്യത്യസ്ത അഭാജ്യസംഖ്യകളും $k_{i}$ കളെല്ലാം ധനപൂർണ്ണസംഖ്യകളുമാണ്‌.

മുകളിൽ പറഞ്ഞ പ്രത്യേകതകൾ ഉപയോഗിച്ച് $\varphi \left(n\right)=\left(p_{1}-1\right)p_{1}^{k_{1}-1}\left(p_{2}-1\right)p_{2}^{k_{2}-1}\ldots \left(p_{r}-1\right)p_{r}^{k_{r}-1}$ എന്ന് കിട്ടുന്നു

ഉദാഹരണം

36 എന്ന സംഖ്യയുടെ ടോഷ്യന്റ് ഫലനം കണ്ടെത്തുന്ന രീതി നോക്കുക. $36=3^{2}2^{2}$. മുകളിലെ സമവാക്യമുപയോഗിച്ചാൽ $\varphi \left(36\right)=2\times 3^{1}\times 1\times 2^{1}=12$ എന്ന് കിട്ടുന്നു.

സവിശേഷതകൾ

• ഓയ്‌ലറുടെ ടോഷ്യന്റ് സിദ്ധാന്തം : $a,n$ എന്നിവ സഹഅഭാജ്യസംഖ്യകളാണെങ്കിൽ $a^{\varphi (n)}\equiv 1{\pmod {n}}$
• ഒരു സംഖ്യയുടെ ഘടകങ്ങളുടെ ടോഷ്യന്റ് ഫലനങ്ങളുടെ തുക ആ സംഖ്യ തന്നെയായിരിക്കും.

അതായത്, $\sum _{d\mid n}\varphi (d)=n$

ഇവിടെ $d\mid n$ എന്നാൽ n ന്റെ എല്ലാ ഘടകങ്ങളുമാണ്‌

• രണ്ടിനെക്കാൾ വലുതായ എല്ലാ സംഖ്യകളുടെയും ടോഷ്യന്റ് ഫലനം ഒരു ഇരട്ടസംഖ്യയായിരിക്കും
• ആറിനെക്കാൾ വലുതായ ഒരു സംഖ്യയുടെ ടോഷ്യന്റ് ഫലനം ഒരിക്കലും ആ സംഖ്യയുടെ വർഗ്ഗമൂലത്തെക്കാൾ ചെറുതാവുകയില്ല
• $\varphi (n^{k})=n^{k-1}\varphi (n)$
• k ഏതെങ്കിലും സംഖ്യകളുടെ ടോഷ്യന്റ് വാലൻസ് ഫലനത്തിന്റെ വിലയാണെങ്കിൽ, അനന്തം സംഖ്യകൾ k ടോഷ്യന്റ് വാലൻസ് ഫലനത്തിന്റെ വിലയായുള്ളവ ഉണ്ടായിരിക്കും. 1958-ൽ പോൾ എർഡോസ് ആണ്‌ ഇത് തെളിയിച്ചത്

കാർമൈക്കൽ ടോഷ്യന്റ് ഫലന പരികൽപന

ടോഷ്യന്റ് വാലൻസ് ഫലനത്തിന്റെ വില ചുരുങ്ങിയത് 2 ആയിരിക്കും എന്ന പരികൽപനയാണ്‌ കാർമൈക്കൽ ടോഷ്യന്റ് ഫലന പരികൽപന (Carmichael's Totient Function Conjecture) എന്നറിയപ്പെടുന്നത്. അതായത്, ഒരു സംഖ്യയുടെ മാത്രം ടോഷ്യന്റ് ഫലനത്തിന്റെ വിലയായി വരുന്ന സംഖ്യകളൊന്നുമില്ല.

1907-ൽ റോബർട്ട് കാർമൈക്കൽ ആണ്‌ ഈ പരികൽപന നടത്തിയത്. ഇതിന്‌ ഒരു തെളിവും അദ്ദേഹം നൽകി. എന്നാൽ ഈ തെളിവ് തെറ്റാണെന്ന് അദ്ദേഹം തന്നെ 1922-ൽ കണ്ടെത്തി. അതിനുശേഷം ഈ പരികൽപന ഇതുവരെ തെളിയിക്കപ്പെട്ടിട്ടില്ല. എന്നാൽ ഈ പരികൽപനയ്ക്ക് വിപരീതമായ സംഖ്യകൾ കണ്ടുപിടിക്കപെടുകയും ചെയ്തിട്ടില്ല. കാർമൈക്കൽ ടോഷ്യന്റ് ഫലന പരികൽപനയ്ക്ക് വിപരീതമായി ഏതെങ്കിലും സംഖ്യ ഉണ്ടെങ്കിൽ അതിൽ ചുരുങ്ങിയത് ആയിരം കോടി അക്കങ്ങൾ ഉണ്ടാകും.

ലെഹ്‌മറുടെ ടോഷ്യന്റ് പ്രശ്നം

$\varphi \left(n\right)$ എന്നത് n-1 ന്റെ ഘടകമാവുന്ന തരത്തിലുള്ള ഭാജ്യസംഖ്യകൾ ഉണ്ടോ എന്ന ചോദ്യമാണ്‌ ലെഹ്‌മറുടെ ടോഷ്യന്റ് പ്രശ്നം (Lehmer's Totient Problem) എന്നറിയപ്പെടുന്നത്. ഈ ചോദ്യത്തിന്‌ ഇതുവരെ ഉത്തരം കണ്ടെത്തിയിട്ടില്ല. എന്നാൽ അത്തരം ഒരു സംഖ്യ ഉണ്ടെങ്കിൽ അത് ഒരു കാർമൈക്കൽ സംഖ്യ ആയിരിക്കും എന്ന് തെളിയിക്കപ്പെട്ടിട്ടുണ്ട്.

പുറം കണ്ണികൾ

• ആദ്യ 500 സംഖ്യകളുടെ ടോഷ്യന്റ് ഫലനങ്ങളുടെ പട്ടിക