- ベストアンサー
ルジャンドルの定理について。
- みんなの回答 （27）
- 専門家の回答
質問者が選んだベストアンサー
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ f(j)=f(k)ならばj=kが成り立つ(1:1に決まる)から fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ すべてのy∈Yに対してy=f(k)となるk∈Xがある時にfは全射という全射の定義から fは全射である ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
その他の回答 (26)
- muturajcp
- ベストアンサー率78% (505/644)
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ すべてのy∈Yに対してy=f(k)となるk∈Xがある時にfは全射という全射の定義から fは全射である ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
- muturajcp
- ベストアンサー率78% (505/644)
n=8 p=2 n!=8!の因数1,2,3,4,5,6,7,8の中のp=2の倍数は 2,4,6,8 の m=[n/p]=[8/2]=4個 だから 2,2*2,2*3,2*4 をかけあわせたものは m!p^m=4!*2^4 となる n!=8!の因数1,2,3,4,5,6,7,8の中で p=2の倍数でないものをかけあわせたものを b=1*3*5*7 とすると n!=b(m!)p^m=(1*3*5*7)(4!)(2^4) となる b=1*3*5*7とp=2は互いに素となる s=3 p^s≦n<p^(s+1) 2^3≦8<2^4だから ↓各辺をp=2で割ると 2^2≦4<2^3 ↓帰納法の仮定から r(4)=[4/2]+[4/2^2]=2+1=3 4!=a(4)2^{r(4)}=a(4)(2^3) となる2と互いに素な自然数a(4)がある これを 8!=b(m!)2^m=(1*3*5*7)(4!)2^4 に代入すると 8!=ba(4)2^{m+r(m)} 8!=(1*3*5*7)a(4)2^{4+3} 8!=(1*3*5*7)a(4)(2^7) a(8)=(1*3*5*7)a(4) r(8)=m+r(m)=4+r(4)=4+3=7 とすると 8!=a(8)p^{r(8)}=(1*3*5*7)a(4)2^7 r(8)=7は8!の素因数として現れるp=2の個数そのものである ---------------- 自然数nと 素数p に対して pの倍数はpの整数倍の事だから ある整数kに対して kp をpの倍数というのだから pの倍数を kp とすると n!の因数1,2,…,nの中のpの倍数は 1≦kp≦n となる 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは整数だから 1≦k≦[n/p] だから 1から[n/p]までの整数kは[n/p]個あるから n!の因数1,2,…,nの中のpの倍数は {kp}_{k=1～[n/p]} の [n/p] 個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
補足
k∈X y=kp=f(k) y=f(k) ∴ fは全射 ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある で、なぜ、全射なのでしょうか？ご教授頂けると幸いです。すみませんが。
- muturajcp
- ベストアンサー率78% (505/644)
自然数nと 素数p に対して pの倍数はpの整数倍の事だから ある整数kに対して kp をpの倍数というのだから pの倍数を kp とすると n!の因数1,2,…,nの中のpの倍数は 1≦kp≦n となる 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは整数だから 1≦k≦[n/p] だから 1から[n/p]までの整数kは[n/p]個あるから n!の因数1,2,…,nの中のpの倍数は {kp}_{k=1～[n/p]} の [n/p] 個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
- muturajcp
- ベストアンサー率78% (505/644)
自然数nと 素数p に対して pの倍数はpの整数倍の事だから ある整数kに対して kp をpの倍数というのだから pの倍数を kp とすると n!の因数1,2,…,nの中のpの倍数は 1≦kp≦n となる k≦0とするとkp≦0となって1≦kpに矛盾するから 1≦kは自然数である 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] だから 1から[n/p]までの自然数kは[n/p]個あるから n!の因数1,2,…,nの中のpの倍数は {kp}_{k=1～[n/p]} の [n/p] 個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
- muturajcp
- ベストアンサー率78% (505/644)
pを素数とする jを非負整数とする F(j)={j=[n/p],nは非負整数→1≦k≦nとなるpの倍数kはj個ある} とする j=0=[n/p]の時 0=[n/p]≦n/p<[n/p]+1=1 0≦n/p<1 ↓各辺にpをかけると 0≦n<p nは自然数だから 1≦n<p 1≦k≦nとなる整数kに対して 1≦k≦n<p だから 1≦k<p となるようなpの倍数kは存在しないから pの倍数は 0個であるから pの倍数は0=[n/p]個であるから F(0)={0=[n/p],nは非負整数→1≦k≦nとなるpの倍数kは0個ある}は真 自然数j≧1に対してF(j-1)が真だと仮定する j=[n/p] nは自然数 とする 1≦j=[n/p]≦n/p<[n/p]+1=j+1 だから 1≦j≦n/p<j+1 ↓各辺にpをかけると p≦jp≦n<(j+1)p ↓各辺からpを引くと 0≦(j-1)p≦n-p<jp ↓n-p=mとすると 0≦(j-1)p≦m<jp ↓各辺をpで割ると 0≦j-1≦m/p<j だから [m/p]=j-1 でmは非負整数で F(j-1)={j-1=[m/p],mは非負整数→1≦k≦mとなるpの倍数kはj-1個ある} は真だから 1≦k≦mとなるpの倍数kはj-1個ある ↓m=n-pだから 1≦k≦n-pとなるpの倍数kはj-1個ある から p+1≦p+k≦nとなるpの倍数kはj-1個ある から p+1≦k≦nとなるpの倍数kはj-1個ある 1≦k≦pとなるpの倍数kは{p}の1個だけあるから 1≦k≦nとなるpの倍数kはj-1+1=j個ある ∴ F(j)={j=[n/p],nは非負整数→1≦k≦nとなるpの倍数kはj個ある}は真 ∴ 1≦k≦nとなるpの倍数kは[n/p]個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
お礼
n!=a(n)p^{r(n)} だからn!はp^{r(n)}でちょうど割り切れるから r(n)はn!の素因数として現れるpの個数そのものです は、n＝8、p＝ 2、r(n)＝4だと、4は、8！の素因数として現れる 2の個数そのものという事でしょうか？具体例を挙げてみました。ご教授頂けると幸いです。すみませんが。
補足
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ fは全射 ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある ここをもう少し詳しくご教授頂けると幸いです。すみませんが。
- muturajcp
- ベストアンサー率78% (505/644)
n!=a(n)p^{r(n)} だからn!はp^{r(n)}でちょうど割り切れるから r(n)はn!の素因数として現れるpの個数そのものです ---------------------------------- n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の [n/p]個 あるという事がなぜわからないのでしょうか? -------------------------- 例) n=9 p=2 とすると n!=9!の因数1,2,3,4,5,6,7,8,9の中でp=2の倍数は 2,4,6,8 の [n/p]=[9/2]=[4.5]=4個 になるのです --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある n!=a(n)p^{r(n)}だから r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
お礼
n!=a(n)p^{r(n)} だからn!はp^{r(n)}でちょうど割り切れるから r(n)はn!の素因数として現れるpの個数そのものです は、n＝8、p＝ 2、r(n)＝4だと、4は、8！の素因数として現れる 2の個数そのものという事でしょうか？具体例を挙げてみました。ご教授頂けると幸いです。すみませんが。
補足
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ fは全射 ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある ここをもう少し詳しくご教授頂けると幸いです。すみませんが。
- muturajcp
- ベストアンサー率78% (505/644)
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ fは全射 ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある r(n)はn!の素因数として現れるpの個数に一致する r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
お礼
r(n)はn!の素因数として現れるpの個数に一致するというのはどういう事でしょうか？ご教授頂けると幸いです。すみませんが。
補足
自然数nと 素数p に対して n!の因数1,2,…,nの中のpの倍数の集合を Y={kp|1≦kp≦n,kは自然数} とする X={k|1≦k≦[n/p],kは自然数} とすると Xの要素数は|X|=[n/p]である f:X→Y f(k)=kp と関数f(k)を定義する {j,k}⊂X f(j)=f(k) とすると jp=f(j)=f(k)=kp jp=kp ↓両辺からkpを引くと jp-kp=0 (j-k)p=0 ↓p>0だから j-k=0 ↓両辺にkを加えると j=k ∴ fは単射 y∈Y とすると y=kp 1≦kp≦nとなる自然数kがある 1≦kp≦n ↓各辺をpで割ると 1/p≦k≦n/p ↓kは自然数だから 1≦k≦[n/p] ∴ k∈X y=kp=f(k) y=f(k) ∴ fは全射 ∴ fは全単射 ∴ |Y|=|X| ↓|X|=[n/p] ∴ |Y|=[n/p] ∴ n!の因数1,2,…,nの中のpの倍数は [n/p]個ある ここをもう少し詳しくご教授頂けると幸いですすみませんが。
- muturajcp
- ベストアンサー率78% (505/644)
[n/p]≦n/p<[n/p]+1だから ↓各辺にpをかけると [n/p]p≦n<([n/p]+1)p [n/p]pと([n/p]+1)pはともにpの倍数だけれども [n/p]p≦nだから [n/p]pはn!の因数1,2,…,nの中にあるけれども n<([n/p]+1)pだから ([n/p]+1)pはn!の因数1,2,…,nの中には無いから n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 なのです --------------------------------- (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 [n/p]≦n/p<[n/p]+1だから ↓各辺にpをかけると [n/p]p≦n<([n/p]+1)p [n/p]pと([n/p]+1)pはともにpの倍数だけれども [n/p]p≦nだから [n/p]pはn!の因数1,2,…,nの中にあるけれども n<([n/p]+1)pだから ([n/p]+1)pはn!の因数1,2,…,nの中には無いから n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個 だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} だから a(n)とpは互いに素となる 非負整数a(n),r(n)がある r(n)はn!の素因数として現れるpの個数に一致する←…ここです r(n) をn!のp指数という r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
- muturajcp
- ベストアンサー率78% (505/644)
(i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0…(1) 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0=a(n)p^{r(n)} だから n!=a(n)とpは互いに素となる 非負整数n!=a(n),0=r(n)がある 0=r(n) をn!のp指数という だから r(n)=0となるから ↓これと(1)から r(n)=0=Σ_{k=1～s}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
補足
n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個である. また.p^2の倍数は p^2,2p^2,3p^2,…[n/p^2]p^2 の[n/p^2]個である 一般にp^kの倍数は p^k,2p^k,3p^k,…[n/p^k]p^k の[n/p^k]個である で、なぜ、［n/p］個なのでしょうか？ご教授頂けると幸いです。すみませんが。
- muturajcp
- ベストアンサー率78% (505/644)
p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する このような仮定が成り立つと分かる のではないのです F(s)=「p^s≦n<p^(s+1)の時r(n)=Σ_{k=1～s}[n/p^k]」 を sについての帰納法によって 証明するのです まず F(0)=「p^(0)≦n<p^(0+1)の時r(n)=Σ_{k=1～0}[n/p^k]」 が成り立つことを証明するのです それから F(s-1)=「p^(s-1)≦n<p^sの時r(n)=Σ_{k=1～s-1}[n/p^k]」 が成り立つと仮定して F(s)=「p^s≦n<p^(s+1)の時r(n)=Σ_{k=1～s}[n/p^k]」 を証明するのです そうすると F(0)が真→F(1)が真→F(2)が真→F(3)が真→F(4)が真→… となって 1=p^0≦n<p^1≦n<p^2≦n<p^3≦n<p^4≦… 全ての自然数nに対して r(n)=Σ_{k=1～s}[n/p^k] が成り立つとわかるのです (i)の証明 nを自然数 pを素数 s=[log_p(n)] t=log_p(n) とすると 対数の定義から p^t=n s=[t] m≧k>s となる任意の自然数m,kに対して [t]=(t以下の最大の整数)だから [t]≦t<[t]+1 s=[t]≦t<[t]+1=s+1 s≦t<s+1 s<kだから s+1≦kだから s≦t<s+1≦k≦m t<k だから n=p^t<p^k n<p^k だから n/p^k<1 だからs<k≦mの時 [n/p^k]=0 だから ∴ Σ_{k=1～m}[n/p^k]=Σ_{k=1～s}[n/p^k] s=[log_p(n)] p^s≦n<p^(s+1) n!=a(n)p^{r(n)} a(n)とpは互いに素となる 非負整数a(n),r(n)がある r=r(n) をn!のp指数という s=0 1=p^0≦n<p^(0+1)=p の時 Σ_{k=1～s}[n/p^k]=Σ_{k=1～0}[n/p^k]=0 1≦n<p でpは素数だから 1≦k≦n<p となる整数kとpは互いに素だから n!とpは互いに素だから n!=(n!)p^0 だから r=0となるから s=0 1≦n<pの時 r(n)=0=Σ_{k=1～0}[n/p^k] は成り立つ s>0 に対して p^(s-1)≦m<p^s の時 r(m)=Σ_{k=1～s-1}[m/p^k]…(仮定) が成り立つと仮定する p^s≦n<p^(s+1) の時 n!の因数1,2,…,nの中で,pの倍数は p,2p,3p,…,[n/p]p の[n/p]個だから m=[n/p] とすると p,2p,3p,…,[n/p]p をかけあわせたものは p,2p,3p,…,mp をかけあわせたものとなり Π_{k=1～m}kp=(m!)p^m となる n!の因数1,2,…,nの中で, pの倍数でないものをかけあわせたものを bとすると n!=b(m!)p^m となる bとpは互いに素となる 自然数bがある p^s≦n<p^(s+1)だから ↓各辺をpで割ると p^(s-1)≦n/p<p^s だから p^(s-1)≦[n/p]<p^s ↓m=[n/p]だから p^(s-1)≦m!<p^s ↓(仮定)から r(m)=Σ_{k=1～s-1}[m/p^k] m!=a(m)p^{r(m)} ↓これをn!=b(m!)p^mに代入すると n!=ba(m)p^{m+r(m)} だから a(n)=ba(m) とすると bとpは互いに素 a(m)とpは互いに素 だから a(n)とpは互いに素 r(n)=m+r(m) とすると n!=a(n)p^{r(n)} r(n) =m+r(m) =m+Σ_{k=1～s-1}[m/p^k] =[n/p]+Σ_{k=1～s-1}[[n/p]/p^k] =[n/p]+Σ_{k=1～s-1}[n/p^(k+1)] =[n/p]+Σ_{k=2～s}[n/p^k] =Σ_{k=1～s}[n/p^k] r(n)=Σ_{k=1～s}[n/p^k] だから p^s≦n<p^(s+1) の時 r(n)=Σ_{k=1～s}[n/p^k] が成り立つ ∴ n!のp指数 r=r(n) に対して r=Σ_{k=1～s}[n/p^k] が成り立つ
補足
n!=(n!)p^0 だから r=0となるから s=0 1≦n<pの時 r(n)=0=Σ_{k=1～0}[n/p^k] は成り立つ とはどう言う事でしょうか？ご教授頂けると幸いです。すみませんが。
関連するQ&A
- ルジャンドルの定理について。
ルジャンドルの定理を以下のURLより、分かりやすく証明していただけないでしょうか？ご教授頂けると幸いです。すみませんが。 https://mathtrain.jp/legendretheorem
- ベストアンサー
- 数学・算数
- ベルトラン・チェビシェフの定理について。
次の（i)をご教授願いたいのですが。 ルジャンドルの定理を使うのは分かるのですが、ここで和はp∧s≦n＜p∧（s＋ 1)のsまでの有限個とする。という所は、どうやって証明するのでしょうか？すみませんが。
- ベストアンサー
- 数学・算数
- そもそも、ピタゴラスの定理って定理なのでしょうか？
そもそも、ピタゴラスの定理って定理なのでしょうか？ いいかえると、真実なのでしょうか? これは、実は簡単にわかります。証明できません。 なぜなら、非ユークリッド幾何学という反例があるから。 だから、ピタゴラスの定理っていうのは、定理ではなくて、 普通のユークリッド幾何学を展開していく上での、仮定とか前提と考えたほうがいいと思います。 ではなぜ、世の中にたくさんある「ピタゴラスの定理の証明」なるものはなんなのでしょうか？ それは、ユークリッド幾何学を特徴づけるピタゴラスの定理よりも、 よりも基本的な公理を仮定していなければなりません。 一般的には、第五公準(平行線は唯一唯一つ)ってのがそうだと思われます。 しかし、その前に、点とか直線とか、距離とか、角度とか、合同とか、たくさんの概念が定義されなくてははなりません。 ところで、数学基礎論では、まず、集合とその間の演算を公理的に定義し、また、自然数と和や積を定義します。 それによって、数論の基本的な結合法則、可換法則、分配法則といったものも、「証明できる」ものになります。 １＋１＝２というのも「証明できる」ものになります。 同じようにしていけば、ピタゴラスの定理って基礎論的に、公理的に、「証明できる」定理なのでしょうか？ 実は、「幾何学基礎論」という本を軽く読んだり、いろいろ検索してみたのですが、ピタゴラスの定理は載ってませんでした。 もしかして、ピタゴラスの定理っていうのは、基礎論的にも、公理的にも、「証明されていない」ものなのでしょうか？ ちなみに、sinθ, cosθを、無限級数の和として定義してやって、 それによってユークリッド幾何の回転を定義し、sin^2θ+cos^2θ=1となるので「証明できた」というのは、たぶん、万人は認めないと思います。
- ベストアンサー
- 数学・算数
- フェルマーの最終定理について
数学は得意ではないし本当の内容は分かりませんが、フェルマーの最終定理の経緯を本で読むととても興味深いですね。そこで素人の質問なのですが、 1) この定理の証明のために数学が発展してきたことは分かりましたが、定理自体は他の何かの定理の証明に使われたりなどしているのでしょうか？ 2) 将来、何か実生活に役立つようなことはあるでしょうか（解がないことで何か保障されるといったような）？ 3) フェルマーがこの定理を発見していなかったら、後年だれかが発見していたでしょうか？ 4) フライのアイデアがなかったら、谷山・志村予想が証明された後もフェルマーの最終定理は証明されずにずっと残っていたでしょうか？ 5) 将来、ワイルズの証明よりもっと簡易な証明、あるいは谷山・志村予想と関係ない証明は現れるでしょうか？ アンケート的な疑問が多くて恐縮ですが、数学に詳しい方のお考えを聞けたら幸いです。
- ベストアンサー
- 数学・算数
- ルジャンドルの母関数
ルジャンドルの母関数(1-2xt+t^2)^(-1/2) = ΣPn(x) t^n ）の公式を証明したいのですが分りません。具体的にどんな方法があるのか知っている方がおられましたら教えて下さい．
- ベストアンサー
- 数学・算数
- 「ピタゴラスの定理」という本を探しています
中学校でピタゴラスの定理の証明を習ったとき，先生が 「この定理はほんとにいろんな人がいろんな証明を考え出しててなあ， 証明ばっかり集めた『ピタゴラスの定理』っていう本が出てるくらいなんや」 と言っていたのを憶えているのですが， 当時探してみたところそのような本は書店に並んでおらず， 十年以上経った現在も発見できません． どなたがご存知の方がいらっしゃいましたら 教えてください．どうしても読んでみたいのです．
- 締切済み
- 数学・算数
- 素数定理をこのように解釈しても良いか。
素数定理とは、 「大きな自然数ｘが素数である確率は１／（log ｘ）」 という物ですが、これを元に次の事が言えるでしょうか？ １ ２と５を除けば素数は一の位が１，３，７，９の どれかになり、各グループの素数は無限個ある。 ２ 素数が現れる確率は４つのグループそれぞれで 等しい。 直感的にはどちらも正しいような気がしますが いかがでしょうか？ １に関してですが素数が無限個あることの証明は、 非常に簡単です。有限個だとしたらそれらの全ての 積に１を加えたものも素数になってしまうので 素数は、無限個あります。しかし各４つのグループ ごとにある事を証明しようとするとちょっと手が 止まってしまいます。 ２は、完全にお手上げです。素数定理には、 一の位が何であるかで場合分けしていないので まぁ正しいような気がしますが。。。 どなたかご意見お願いします。
- 締切済み
- 数学・算数
- フェルマーの最終定理について
フェルマーの最終定理について質問をします． フェルマーは、この定理を発見したときに、ｎ＝４の場合だけは証明したと本に書かれてあったのですが、その証明がよく分からないのです。というか、どのような証明をしたのかが分かりません。 この証明の仕方を、詳しく知っている方がいましたら、教えてください。 よろしくお願い致します。
- 締切済み
- 数学・算数
- なんとかの定理を解く？？
こんな質問をして世間知らずと笑われないか不安ですが、数年間腑に落ちなかったので 恥を忍んで質問させていただきます。 よく、RED博士の＠＠＠の最終定理の解く鍵をポチョ博士が解いたとか言いますよね 誰も解いたことがない定理だ！ て具合に それが疑問なんです ・誰かが一度、その定理を解いて(作って）説明したからこその定理ではないのか？ならば答えはすでにあるのでは？ 最後の詰めでその正しさが証明されていなければ唯の仮定では？ ・それとも、定理の結果は発表しても、その計算過程は発表しないのか？ いや・・・余りにも複雑なため、発見者も途中過程を紛失することがある？ とまぁ、常々疑問だったのです、解かれたはずの定理を もう一度解く事が。 それとも、私の考えている仕組み事態が違うのか？ ・・・・生物や、化学のように誰かが立てた過程、定説を証明したという言い方なら納得できるのですが。 どうなのでしょうか
- ベストアンサー
- 数学・算数
- 私が知りたいのは ゲーデルの不完全性定理の幾何学での理解です。
私が知りたいのは ゲーデルの不完全性定理の幾何学での理解です。 (1)第２不完全性定理では 次の表現があり『公理系Ｎにおいて、その無矛盾性を証明することは不可能である』、そのなかで問題として『 真であるが証明不可能な主張とは何か。』に対して 答え『公理』とあり 自己言及を表現していることは 理解し易いのです。幾何学では５公理です。この理解はたぶん正しいと思います。 ところが (2)私がよく分らないのは 第１不完全性定理です。『形式的体系Ｓにおいて、形式的体系Ｓが無矛盾である限り、「形式的体系Ｓにおいて命題は証明可能である。」という命題も「形式的体系Ｓにおいて命題は証明不可能である。」という命題も証明不可能である。』 と表される（別表現もありますが）とあります。 ここで現れる命題は抽象的言語であってよく分らないのです。例えばユークリッド幾何学においてはこの具体例は何でしょうか。私の理解は 「例えば無限遠点において平行線は交わるは証明可能である」はその例のようにおむのですが。つまり 例題には ユークリッド幾何学では未定義の無限遠点が現れており 証明はできない のです。いくら公理を増やして定義を明白にしても 未定義の領域はある ということです。 もう一つの例ですが 無限遠点は扱わないという６番目の公理を追加したとしても 例えば 「X・X＝－１ は根がない は証明可能である」も証明できない と思うのです。なぜなら複素数は未定義だからです。つまり 『公理で定義されても未定義域は必ずある』が第一不完全性定理の一つの別表現ではないか と思うのです。この理解が間違っているのかどうか どなたかにお教えて頂きたかったのですが
- ベストアンサー
- 数学・算数
補足
fは単射と書かれていますが、これは、 1： 1に決まるからですよね？ご教授頂けると幸いです。すみませんが。