- 締切済み
この定理の名前を教えてください
aとpは互いに素とする aとpは共に整数とする pは素数とする このときに a^(p-1)≡1 (mod p)が成立 これは定理として名前がついているのですか？ 証明は簡単にできました。
- ny_bigappl
- お礼率0% (1/441)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- neta
- ベストアンサー率50% (13/26)
- Segenswind
- ベストアンサー率50% (281/562)
関連するQ&A
- フェルマの小定理について
次の主張（フェルマの小定理）の証明を与えよ。 「ｐが素数のとき、aがpと互いに素な整数ならば、a^(p-1) ≡ 1 (mod p) が成立する。」 フェルマの小定理についてあまり詳しくないので分かりやすく教えていただけると嬉しいです。 宜しくお願い致します。
- 締切済み
- 数学・算数
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- フェルマの小定理と位数に関する質問です
問題） pを素数とします。また、aをpで割り切ることのできない整数とします。 この時、a^n≡1(mod p)となる最小の正整数nをmとすると p≡1(mod m)であることを証明したいです。 証明) まず、フェルマの小定理より、 n=p-1のとき、a^n≡1(mod p)が成り立つことが分かります。 よって、n=p-1がa^n≡1(mod p)となる最小の正整数nの場合、 m=p-1なので、明らかにp-1をmで割り切ることができるため、 p≡1(mod m)である。 (ここからが分かりません。。。) 次に、n=p-1がa^n≡1(mod p)となる最小の正整数nでない場合、 つまり、m<p-1となるmが存在する場合、 そのmによって、p≡1(mod m)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- フェルマの小定理の証明方法について
フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (a,m)=1のとき a^(φ(m))≡1 (mod m) 【フェルマの小定理】 a^(p-1)≡1 (mod p) ただし、aは正の整数（←条件を、少し制約しました。）、pは素数、ａとｐは互いに素（(a,p)=1） とする。 ■証明 数学的帰納法を用いる。 (1)a=1 のときは明らか。 (2)a=k のとき成り立つと仮定して、a=k+1のとき成り立つことを証明する。 言い換えると、mod p において、 k^p≡k ⇒ (k+1)^p≡k+1 を証明すればよい。 以下、合同式は mod p の場合のことを指す。 仮定より、 (k)^p≡k (k)^p-1≡k-1 F(k)=k^(p-1)+k^(p-1)…+1 とおくと、 (k-1)・F(k)≡k-1 よって、 F(k)≡1 ところで、F(k)はp個の元から構成されており、 p-1 Σ(k^m)≡1 （式ａ） m=0 と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、 p-1 Σ((k)^m*(1)^m)≡1 （式ｂ） m=0 と書ける。これより、 p-1 k・Σ((k)^m*(1)^m)≡k m=0 p-1 (k*1-1)・Σ((k)^m*(1)^m)≡k m=0 よって、 (k*1)^p-1≡k 書き直して、 (k+1)^p≡k+1 <証明終>
- ベストアンサー
- 数学・算数
- 中国剰余定理 3数
余りが条件式を満たすがわからないので質問します。 p,q,rどの2つをとっても、互いに素な自然数とする。a,b,cを任意の整数とする。このとき、 x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たす整数ｘが、0からpqr-1までの間に1つ存在する。この定理の証明は、 (qr)s≡1 mod(p),(rp)t≡1 mod(q),(pq)u≡1 mod(r),を満たすs,t,uを求めることから始まります。sであれば、(qr)s+py=1・・・(1)という１次不定方程式を解くことで、得られます。q,rがpと互いに素であるから、qr,pが互いに素なので(1)を満たすs,yは存在します。同様にt,uが得られます。x=a(qr)s+b(rp)t+c(pq)u・・・(2)とおけば、xは条件式を満たします。(2)をｐで割った余りは、a*1+0+0=aとなります。qで割れば余りb,rで割れば余りc,となります。ここからがわからない箇所です。このxをpqrで割った余りも条件式をみたします。 まず、自分の計算では、x=a(qr)s+b(rp)t+c(pq)u=pqr{as(1/p)+bt(1/q)+cu(1/r)}となり余りが出ません。そして条件式x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 連立合同式の商の定理について
連立合同式の商の定理について教えてください。 x,yを整数 m,aを自然数とするとき ax≡ay (mod m) ⇔ x≡y ( mod m/GCD(m,a) ) (おかしな表記ですみません。( mod -)は分数式です) が「商の定理」と習いましたが、これは連立合同式 x≡a (mod K) x≡b (mod L) x≡c (mod M) のK L M が「互いに素」ではないときに適用できる定理だと思うのですが、うまく理解できません。 解らない点:(1) 連立合同式 x≡a (mod K) x≡b (mod L) の時、K L のGCDが「1」で「互いに素」と覚えていますが x≡a (mod K) x≡b (mod L) x≡c (mod M) の時も K L MのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？ 解らない点:(2) x≡a (mod K) x≡b (mod L) x≡c (mod M) で K L M が「互いに素」ではない場合、商の定理を適用した解法でx≡y ( mod m/GCD(m,a) )を求める方法。 K L M が「互いに素」ではない時、K L Mの最小公倍数を使えばよいのは解るのですが、GCD(m,a)の「a」が理解できません。「m」はK L Mの最小公倍数だと思うのですが、「a」は何になるのでしょう？ x≡2 (mod 4) x≡4 (mod 12) x≡3 (mod 9) の場合を例として、具体的に解法を教えてください。 よろしくお願いします。もしも上式が連立合同式として成立しないのであれば、その理由も教えてください。 中国式余剰定理では、( mod ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j (mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- RSA暗号の中国剰余定理についておしえてください.
RSA暗号の中国剰余定理についておしえてください． N=77 = 7×11, p1=7, p2=11 d1 = d mod (p1-1) = 43 mod (7-1) = 1 d2 = d mod (p2-1) = 43 mod (11-1) = 3 m1 = c^d1 mod p1 = 48^1 mod 7 = 6 m2 = c^d2 mod p2 = 48^3 mod 11 = 4^3 mod 11 = 9 連立方程式 m = 6 mod 7 m = 9 mod 11 となり p1=7とp2=11は共に素数であるので互いに素 q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2 /// q2=p1-^1 mod p2 = 7^-1mod 11=8 //// これを用いて m=(m1×p2×q1 + m2×p1×q2) mod p1p2 = (6×11×2 + 9×7×8) mod 77 = (132+504) mod 77 = 20 平文 m = 20 とあるのですが，q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2と q2=p1^-1 mod p2 = 7^-1mod 11=8の部分でどうして2と8になるのかがわかりません．1時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜
- 締切済み
- その他([技術者向] コンピューター)
