هزار مقدار اولیه
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
در نظریه اعداد تابع فی اویلر یا
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
تابعی است که تعداد اعداد طبیعی کوچکتر مساوی n که نسبت به n اول اند را میشمارد. اگر n یک عدد طبیعی مثبت باشد، آنگاه
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
برابر است با تعداد اعداد طبیعی k در بازه ۱ تا n بهطوریکه بزرگترین مقسومعلیه مشترک (ب.م.م) n و k برابر ۱ باشد.
تابع فی اویلر یک تابع ضربی است، بدین معنی که اگر دو عدد m و n نسبت به هم اول باشند آنگاه
φ ふぁい
(
m
n
)
=
φ ふぁい
(
m
)
φ ふぁい
(
n
)
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}
.
برای مثال (9)φ ふぁい برابر ۶ است. زیرا اعداد ۱، ۲، ۴، ۵، ۷ و ۸ نسبت به ۹ اول هستند.
تابع فی اویلر نقش کلیدی در تعریف سیستم رمزنگاری RSA دارد.
تاریخچه و نمادگذاری [ ویرایش ]
لئونارد اولر این تابع را در سال ۱۷۶۳ معرفی کرد. در آن زمان او هنوز نماد خاصی برای این تابع تعیین نکرده بود. بعدها لئونارد اویلر با مطالعه بیشتر تابع فی، حرف یونانی π ぱい را برای آن برگزید. نماد استاندارد φ ふぁい بعدها توسط گاوس استفاده شدهاست.
محاسبه مقدار تابع فی [ ویرایش ]
چندین راه برای محاسبه این فرمول وجود دارد.
فرمول ضرب اویلر [ ویرایش ]
این تابع بیان میکند که:
φ ふぁい
(
n
)
=
n
∏
p
∣
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}
که در آن
p
{\displaystyle p}
یک عدد اول است بهطوریکه
n
{\displaystyle n}
بر
p
{\displaystyle p}
بخش پذیر نیست.
تبدیل فوریه [ ویرایش ]
مقدار تابع فی برابر است با مقدار تبدیل فوریه گسسته ب.م.م در ۱ یعنی:
F
{
x
}
[
m
]
=
∑
k
=
1
n
x
k
⋅
e
−
2
π ぱい
i
m
k
n
,
x
=
{
gcd
(
k
,
n
)
}
for
k
∈
{
1
…
n
}
φ ふぁい
(
n
)
=
F
{
x
}
[
1
]
=
∑
k
=
1
n
gcd
(
k
,
n
)
e
−
2
π ぱい
i
k
n
.
{\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}},\mathbf {x} =\left\{\gcd(k,n)\right\}\quad {\text{for}}\,k\in \left\{1\dots n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{{-2\pi i}{\frac {k}{n}}}.\end{aligned}}}
مقدار حقیقی این فرمول برابر است با:
φ ふぁい
(
n
)
=
∑
k
=
1
n
gcd
(
k
,
n
)
cos
2
π ぱい
k
n
.
{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {2\pi {\frac {k}{n}}}.}
توجه کنید که برخلاف دو فرمول دیگر در این فرمول نیازی به دانستن عوامل اول n نیست. اما چون فرمول شامل محاسبه ب.م.م n و همه اعداد مثبت کمتر از n است در نهایت به تجزیه n نیاز خواهیم داشت.
جمع مقسوم علیهها [ ویرایش ]
فرمول کلاسیک اویلر
∑
d
∣
n
φ ふぁい
(
d
)
=
n
,
{\displaystyle \sum _{d\mid n}\varphi (d)=n,}
این فرمول به روشهای مختلف قابل اثبات است.
برای n>1 میتوان تابع فی را به عنوان یک حد تابع زتای ریمان محاسبه کرد
φ ふぁい
(
n
)
=
n
lim
s
→
1
ζ ぜーた
(
s
)
∑
d
|
n
μ みゅー
(
d
)
(
e
1
/
d
)
(
s
−
1
)
{\displaystyle \varphi (n)=n\lim \limits _{s\rightarrow 1}\zeta (s)\sum \limits _{d|n}\mu (d)(e^{1/d})^{(s-1)}}
که در این فرمول
ζ ぜーた
(
s
)
{\displaystyle \zeta (s)}
تابع زتای ریمان است،
μ みゅー
{\displaystyle \mu }
تابع موبیوس است،
e
{\displaystyle e}
عدد نپر است،
و d مقسوم علیه است.
چند مقدار تابع [ ویرایش ]
۹۹ مقدار اولیه این تابع در جدول و نمودار زیر قابل مشاهده است.
Graph of the first 100 values
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
+۰
+۱
+۲
+۳
+۴
+۵
+۶
+۷
+۸
+۹
۰+
۱
۱
۲
۲
۴
۲
۶
۴
۶
۱۰+
۴
۱۰
۴
۱۲
۶
۸
۸
۱۶
۶
۱۸
۲۰+
۸
۱۲
۱۰
۲۲
۸
۲۰
۱۲
۱۸
۱۲
۲۸
۳۰+
۸
۳۰
۱۶
۲۰
۱۶
۲۴
۱۲
۳۶
۱۸
۲۴
۴۰+
۱۶
۴۰
۱۲
۴۲
۲۰
۲۴
۲۲
۴۶
۱۶
۴۲
۵۰+
۲۰
۳۲
۲۴
۵۲
۱۸
۴۰
۲۴
۳۶
۲۸
۵۸
۶۰+
۱۶
۶۰
۳۰
۳۶
۳۲
۴۸
۲۰
۶۶
۳۲
۴۴
۷۰+
۲۴
۷۰
۲۴
۷۲
۳۶
۴۰
۳۶
۶۰
۲۴
۷۸
۸۰+
۳۲
۵۴
۴۰
۸۲
۲۴
۶۴
۴۲
۵۶
۴۰
۸۸
۹۰+
۲۴
۷۲
۴۴
۶۰
۴۶
۷۲
۳۲
۹۶
۴۲
۶۰
خط y = n-1 یک کران بالا برای تابع است و زمانی رخ میدهد که n اول باشد.
بیان میکند: اگر n و a نسبت به هم اول باشند آنگاه
a
φ ふぁい
(
n
)
≡
1
mod
n
.
{\displaystyle a^{\varphi (n)}\equiv 1\mod n.\,}
در حالت خاصی که n عدد اول باشد این قضیه به قضیه کوچک فرما معروف است.
این قضیه از قضیه لاگرانژ نتیجه میشود.
سیستم رمزنگاری RSA بر روی همین قضیه بنا شده است: بیان میکنید که معکوس تابع
a
↦
a
d
mod
n
{\displaystyle a\mapsto a^{d}\mod n}
در واقع همان تابع
b
↦
b
e
mod
n
{\displaystyle b\mapsto b^{e}\mod n}
است که e معکوس ضربی d به پیمانه
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
است.
دیگر فرمولهای مرتبط با
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
[ ویرایش ]
a
∣
b
{\displaystyle a\mid b}
→
φ ふぁい
(
a
)
∣
φ ふぁい
(
b
)
.
{\displaystyle \varphi (a)\mid \varphi (b).}
n
∣
φ ふぁい
(
a
n
−
1
)
{\displaystyle n\mid \varphi (a^{n}-1)}
(a , n > 1)
φ ふぁい
(
m
n
)
=
φ ふぁい
(
m
)
φ ふぁい
(
n
)
⋅
d
φ ふぁい
(
d
)
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}}
d = gcd(m , n ).
φ ふぁい
(
2
m
)
=
{
2
φ ふぁい
(
m
)
if
m
is even
φ ふぁい
(
m
)
if
m
is odd
{\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}
φ ふぁい
(
n
m
)
=
n
m
−
1
φ ふぁい
(
n
)
.
{\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n).}
φ ふぁい
(
l
c
m
(
m
,
n
)
)
⋅
φ ふぁい
(
g
c
d
(
m
,
n
)
)
=
φ ふぁい
(
m
)
⋅
φ ふぁい
(
n
)
.
{\displaystyle \varphi (\mathrm {lcm} (m,n))\cdot \varphi (\mathrm {gcd} (m,n))=\varphi (m)\cdot \varphi (n).}
∑
d
∣
n
μ みゅー
2
(
d
)
φ ふぁい
(
d
)
=
n
φ ふぁい
(
n
)
{\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}
∑
1
≤
k
≤
n
(
k
,
n
)
=
1
k
=
1
2
n
φ ふぁい
(
n
)
for
n
>
1
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}n>1}
∑
k
=
1
n
φ ふぁい
(
k
)
=
1
2
(
1
+
∑
k
=
1
n
μ みゅー
(
k
)
⌊
n
k
⌋
2
)
{\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)}
∑
k
=
1
n
φ ふぁい
(
k
)
k
=
∑
k
=
1
n
μ みゅー
(
k
)
k
⌊
n
k
⌋
=
6
π ぱい
2
n
+
O
(
(
log
n
)
2
/
3
(
log
log
n
)
4
/
3
)
{\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+{\mathcal {O}}\left((\log n)^{2/3}(\log \log n)^{4/3}\right)}
∑
k
=
1
n
k
φ ふぁい
(
k
)
=
315
ζ ぜーた
(
3
)
2
π ぱい
4
n
−
log
n
2
+
O
(
(
log
n
)
2
/
3
)
{\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+{\mathcal {O}}\left((\log n)^{2/3}\right)}
اشنایدر دو رابطه پیدا کرد که نسبت طلایی و تابع فی و تابع موبیوس را به هم مرتبط میکرد.
در فرمولهای زیر
ϕ
=
1
+
5
2
=
1.618
…
{\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}=1.618\dots }
نسبت طلایی است.
این روابط به صورت زیر هستند:
ϕ
=
−
∑
k
=
1
∞
φ ふぁい
(
k
)
k
log
(
1
−
1
ϕ
k
)
{\displaystyle \phi =-\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)}
و
1
ϕ
=
−
∑
k
=
1
∞
μ みゅー
(
k
)
k
log
(
1
−
1
ϕ
k
)
.
{\displaystyle {\frac {1}{\phi }}=-\sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right).}
از کم کردن این دو نتیجه میشود
∑
k
=
1
∞
μ みゅー
(
k
)
−
φ ふぁい
(
k
)
k
log
(
1
−
1
ϕ
k
)
=
1.
{\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)-\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)=1.}
با اعمال تابع نمایی به هر دو طرف رابطه به یک رابطه برای عدد نپر میرسیم
e
=
∏
k
=
1
∞
(
1
−
1
ϕ
k
)
μ みゅー
(
k
)
−
φ ふぁい
(
k
)
k
.
{\displaystyle e=\prod _{k=1}^{\infty }\left(1-{\frac {1}{\phi ^{k}}}\right)^{\frac {\mu (k)-\varphi (k)}{k}}.}
اثبات بر پایه دو فرمول زیر است:
∑
k
=
1
∞
φ ふぁい
(
k
)
k
(
−
log
(
1
−
x
k
)
)
=
x
1
−
x
{\displaystyle \sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}(-\log(1-x^{k}))={\frac {x}{1-x}}}
and
∑
k
=
1
∞
μ みゅー
(
k
)
k
(
−
log
(
1
−
x
k
)
)
=
x
,
{\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}(-\log(1-x^{k}))=x,}
سری دیریکله برای تابع فی را میتوان بر حسب جملات تابع زتای ریمان به صورت زیر نوشت
∑
n
=
1
∞
φ ふぁい
(
n
)
n
s
=
ζ ぜーた
(
s
−
1
)
ζ ぜーた
(
s
)
.
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}
)
همچنین تابع مولد سری لامبرت به صورت زیر است
∑
n
=
1
∞
φ ふぁい
(
n
)
q
n
1
−
q
n
=
q
(
1
−
q
)
2
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}
که در ان اندازه q کمتر از ۱ است.
هر دو روابط بالا با استفاده ضرب سریهای پایه و با استفاده از فرمولهای محاسبه تابع فی قابل اثبات هستند.
نسبت دو جمله متوالی [ ویرایش ]
در سال ۱۹۵۰ سومایاجولو اثبات کرد
lim
inf
φ ふぁい
(
n
+
1
)
φ ふぁい
(
n
)
=
0
{\displaystyle \lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}=0}
و
lim
sup
φ ふぁい
(
n
+
1
)
φ ふぁい
(
n
)
=
∞
.
{\displaystyle \lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}=\infty .}
رمزنگاری RSA [ ویرایش ]
در سیستم RSA ابتدا دو عدد اول بزرگ p و q را انتخاب میکنیم. سپس مقادیر n=pq و k=
φ ふぁい
(
n
)
{\displaystyle \varphi (n)}
را محاسبه میکنیم؛ و دوعدد e و d را پیدا میکنیم بهطوریکه ed به پیمانه k برابر ۱ باشد. n و e به عنوان کلید عمومی اعلان میشوند و n و d به عنوان کلید خصوصی مخفی نگاه داشته میشود.
یک پیام مانند عدد مثبت m به صورت S = me mod n رمزگذاری میشود.
برای رمزگشایی مقدار t = Sd mod n محاسبه میشود. قضیه اویلر نشان میدهد که اگر t کمتر از n باشد آنگاه t=m.
سیستم RSA به خطر خواهد افتاد اگر بتوانیم عدد n را تجزیه کنیم یا بتوانیم مقدار تابع فی را بدون تجزیه n بدست بیاوریم.
مسئلههای حل نشده [ ویرایش ]
اگر p اول باشد آنگاه
φ ふぁい
(
p
)
=
p
−
1
{\displaystyle \varphi (p)=p-1}
. لیمر در سال ۱۹۳۲ سؤال زیر را مطرح کرد:
آیا عدد مرکب n وجود دارد بهطوریکه
φ ふぁい
(
n
)
|
n
−
1
{\displaystyle \varphi (n)|n-1}
؟
در سال ۱۹۳۳ لیمر اثبات کرد که اگر n وجود داشته باشد آنگاه حتماً باید فرد باشد و باید حداقل ۷ عامل اول داشته باشد. در سال ۱۹۸۰ کوهن و هاگیس اثبات کردند که n>1020 و باید حداقل ۱۴ عامل اول داشته باشد. بعدها هاگیس نشان داد که اگر n بر ۳ بخش پذیر باشد آنگاه n>101937042 و باید حداقل ۲۹۸۸۴۷ عامل اول داشته باشد.
حدس کارمایکل [ ویرایش ]
حدس: هیچ عددی مانند n وجود ندارد بهطوریکه برای هر عدد دیگر مانند m داشته باشیم
φ ふぁい
(
n
)
!
=
φ ふぁい
(
m
)
{\displaystyle \varphi (n)!=\varphi (m)}
.
اگر یک مثال نقض برای این گزاره پیدا شود آنگاه میتوان نشان داد که بینهایت مثال نقض برای این گزاره وجود دارد.
میتوان نشان داد که کوچکترین مثال نقض برای این گزاره در مبنای ۱۰ بیش از ۱۰ میلیارد رقم دارد.
جستارهای وابسته [ ویرایش ]