ベストアンサー フェルマの小定理です。画像のことが導かれるらしいん 2013/02/08 07:45 ですが、なんでn^(p-1)-1がpで割り切れるんですか?互いに素なn、pが、n=p=1となるときがあるんですよね? 画像を拡大する みんなの回答 (2) 専門家の回答 質問者が選んだベストアンサー ベストアンサー Tacosan ベストアンサー率23% (3656/15482) 2013/02/08 12:08 回答No.2 p の条件を確認してください. 質問者 お礼 2013/02/08 12:25 ありがとうございます。 よくみたらpは素数ってかいてありました。 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 その他の回答 (1) Tacosan ベストアンサー率23% (3656/15482) 2013/02/08 11:03 回答No.1 「n=p=1となるときがある」と, 何か困るんでしょうか? 質問者 お礼 2013/02/08 11:10 ありがとうございます。 n=p=1のとき、n{n^(p-1)-1}の{}内じゃないnがpで割りきれてしまって、n^(p-1)-1がpで割り切れることをいえなくなって困ると思いました。 もしn≠pなら、n{n^(p-1)-1}は、{}内じゃないn自体がpで割り切れないから、のこったn^(p-1)ー1がpで割り切れることになるとおもいました。 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 カテゴリ 学問・教育数学・算数 関連するQ&A フェルマーの小定理 http://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node96.html このサイトの"証明: 定理 17.2 をx = m^(q-1) mod pに対して適応すると"という行からひとつしたの (m^(q-1))^(p-1) = m^(n') = 1 mod p これはフェルマーの小定理を用いて導いてるのは分かります.しかし,m と p が互いに素でなければ成り立たないはずなのにそこに言及していないのが気になります.なぜ成り立つのでしょうか? フェルマの小定理について 次の主張(フェルマの小定理)の証明を与えよ。 「pが素数のとき、aがpと互いに素な整数ならば、a^(p-1) ≡ 1 (mod p) が成立する。」 フェルマの小定理についてあまり詳しくないので分かりやすく教えていただけると嬉しいです。 宜しくお願い致します。 フェルマの小定理と位数に関する質問です 問題) 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)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。 天文学のお話。日本ではどのように考えられていた? OKWAVE コラム フェルマーの最終定理(n=4) p,qは互いに素な自然数とする。以下の問いに答えよ。 (1)p,qがともに奇数であるとき、p^4+q^4は自然数の2乗にならないことをするせ。 これは、平方数を4で割った余りは、0または1で、条件よりp^2,q^2も奇数で p^4+q^4≡1+1=2(mod 4) mod 4で0または1でないので、平方数ではない。と書かれています。 (2)qは奇数とする。つぎの手順に従って、(2p)^4+q^4が自然数の2乗にならないことを背理法を用いてしるせ。 [1]次の仮定(H)が成り立つものとして、以下の問(A)~(D)に答えよ。 仮定(H):(2p)^4+q^4=r^2となる自然数rが存在する。 (A)2pとrは互いに素になることをしるせ。 仮定(H)より2pが偶数で、qが奇数なので、rは奇数です。ここからがわからないところです。2pとrの最大公約数をdとおくと、dは奇数です。 自分は、偶数を 2*奇数、2*偶数、奇数を2*奇数+1、2*偶数+1、として、最大公約数が奇数なら、偶数も奇数も奇数で割って、自然数になるのか確かめようとしましたが、失敗しました。 どなたか偶数と奇数の最大公約数は奇数になることを証明してください。お願いします。 フェルマーの定理の変形バージョン n>=3以上とするとき、 x^n+y^(n+1)=z^n を満たす自然数x,y,zは存在しますか? フェルマーの定理と違うところは、y^n ではなく、y^n*y=y^(n+1) となっているところです。 この公式を満たすxyzは存在しますか? フェルマーの大定理 n=3の場合の証明 フェルマーの大定理・n = 3の場合の証明について質問です。 オイラーはx^3 + y^3 = z^3をx = a + b、y = a - bとおき、整理することによって、 z^3 = 2a(a^2 + 3b^2) と変形し、n = 3の場合のフェルマーの大定理を証明しました。 そこで、質問です。 【2a】と【a^2 + 3b^2】が、互いに素な場合は無限降下法をつかって証明できるようですが、 【2a】と【a^2 + 3b^2】が、互いに素ではなく、1以外の公約数を持つ場合、どのようにして証明すればよいのでしょうか? 皆様のご教授をお待ちしております。 p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか? nがpともqとも互いに素であるときは、 Fermatの小定理を使えばn^{(p-1)(q-1)}≡1 (mod pq) が言えるので、標記の命題は言えると思うのですが pまたはqのいずれか一方がnと互いに素でないとき n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます (私がやったケースはp=3,q=11の場合です)。 これは正しいのでしょうか? 正しいとしたら何故ですか? フェルマーの最終定理 N=3の場合 http://enjoymath.blog71.fc2.com/blog-entry-54.html この証明の後半のほうで (これより、2t, t+3, t-3は互いに素であるから) とありますが、なぜこれら3つの数が互いに素といえるのかが 分かりません。 (これより)、とは具体的にどの部分をさして、なぜ3つの数が互いに素になるのかの 詳しい解説をよろしくお願いします。 フェルマー小定理の特殊形? 高校受験の娘から整数問題の質問をされ、答えたついでに類題を 出してやろうとあれこれ考えていたところ、以下のような規則を みつけました。 n^(4m+1)≡n (mod 10) : n,mは 整数 恥ずかしながら自分で証明できなかったので、娘に出題することは やめましたが、それ以前この式は本当に正しいのだろうかという疑問が あります。 フェルマー小定理の特殊形のような、そうでないような・・・。 ●すでに知られた一般的な規則で、正しいものでしょうか? ●証明はかなり難しいものでしょうか? (中学レベル、高校レベル、それ以上、程度で結構です) 注)私自身は数学に興味はもっていますがほとんど素人の人間です。 あまり難しい説明は理解の範囲を超えると思いますが、この規則の 原型となる公式や、成立する範囲、条件などについてお教えいただ ければ幸いです。 (もし証明可能であればヒントをいただければ一度チャレンジして みようかなとも考えております) よろしくお願いします。 フェルマーの定理の式でn=-1,-2のときは? x^n+y^n=z^nの自明でない整数解を求める問題があります。 n≧3のときには、存在しません。フェルマーが予想し、ワイルズが証明しました。 n=2のときには、ピタゴラス数といってたくさん解がありますが、たとえば、 d , m , n を任意の自然数として, x = d(m^2 - n^2), y = 2dmn, z = d(m^2 + n^2) といった解があります。 また、一つのピタゴラス数から次々に別のピタゴラス数を生成し、それで全部が尽くされる方法も知られています。 http://mathworld.wolfram.com/PythagoreanTriple.html n=1のときには、つまんない問題になります。 n=0のときには、存在しません。 n≦-3のとき、存在しないことは、すぐに考えれば分かると思います。 なので、問題なのは、n=-1,-2のときで、このとき解は無数に存在しますが、どう書き表せるのでしょうか? または、解を次々生成していく方法や、性質などはあるのでしょうか? 数A 整数の性質 kを2以上の整数とする。2からkまでの整数のうち、kと互いに素であるものの個数をNとする。 例えば、k=5とすると2から5までの整数のうち、5と互いに素であるものは2、3、4で あるから、N=3である。 (1)k=7のとき、Nを求めよ。また、k=14のとき、Nを求めよ。 (2)pを7でない素数とする。k=7pのとき、Nを求めよ。 (3)p、qはともに素数であり、p<qとする。k=pqのとき、N=11を満たすp、qの組(p、q)をすべて 求めよ。 この問題があまり分かりません。解答・解説を見ても分かりませんでした。 分かる方がいれば、解説まで教えて下さい。 宜しくお願いします。 双子素数予想の類似、算術級数定理の類似 素数を小さい順にp(1),p(2),,,とします。 {p(m)-p(n)|m>n}、 {p(m)+p(n)|m≦n}、 {p(m)+p(n)|m<n}、 {p(n+1)-p(n)|nは自然数}、 {p(n+1)+p(n)|nは自然数}、 などを考えます。 目的は、素数に関する様々な定理や予想をそれらで言い換えたいのです。 双子素数は無限個ある(双子素数予想) ⇔{p(n+1)-p(n)|nは自然数}において、p(n+1)-p(n)=2となるnは無限個 ♯そうすると疑問に思うのは、 たとえば{p(n+1)-p(n)|nは自然数}のある偶数の元について、それを満たすnが有限個のものは存在するのでしょうか? 初項aと公差dが互いに素であるような等差数列のなかに素数が無限に存在する(算術級数定理) ⇒{p(m)-p(n)|m>n}において、p(m)-p(n)="dの倍数"となる(m,n)は無限個 ♯そうすると疑問に思うのは、 たとえば{p(m)+p(n)|m>n}において、p(m)+p(n)="dの倍数"となる(m,n)は無限個でしょうか? ♯これはd=2であれば明らかに正しそうです。 d=3とかのときはどうなのでしょう? ♯さらに、2つの合成数の差の集合、または、和の集合とかを考えたときに、成り立つ定理、予想される事実はあるのでしょうか? ♯こういった言いかえができる定理とかは他にありますでしょうか? 日本史の転換点?:赤穂浪士、池田屋事件、禁門の変に見る武士の忠義と正義 OKWAVE コラム フェルマーの小定理 RSAの勉強をしています。そこで質問なんですが p,qは異なる素数で a^b≡x (mod p) a^b≡x (mod q) のとき、 a^b≡x (mod p*q)になるのは明らかなんでしょうか。 フェルマーのやらなかったこと おなじみのフェルマの定理: n を正の整数とすれば、 2<n のとき x^n + y^n = z^n をみたす整数の組(x,y,z)は存在しない。 ですけども、 ここで、n を整数全体にに拡張して、 n=1 のときは、いくらでも整数解があります。 n=0 のときは、無意味です。(整数解は無い) n=-1 のときは、たとえば、(x,y,z)=(4,4,2)はひとつの解ですよね。 さて、n=-2,-3,-4,-5,・・・ などのときを調査するのは、数学的に意味のある営みでしょうか? 忌憚なきご意見・見通しをお願いいたします。 必要ならば、高額のため、「ガウス整数」なども俎上にあげていただくことも期待しています「。 証明したいことを証明の途中に使う nとaが互いに素 ⇔ nとn-aが互いに素 の証明で2つ疑問がわいたので、質問します。 nとaの最大公約数をdとおくと n=Nd a=Ad (NとAは互いに素 これは背理法の証明 がインターネットでしらべれました。) とおけます。このときn-a=(N-A)dです。 ここからが疑問です。NとAが互いに素より、NとN-Aも互いに素です。 自分はこの文は、nをN、aをAと置き換えてはいるが証明したいことであり、成り立つかわからないので証明の途中には使っていけないと思いました。証明の続きは、 よってdはnとn-aの最大公約数にもなるから、nとaが互いに素 ⇔ nとn-aが互いに素です。で終わっていますが、2つ目の疑問が残りました、自分はd=1を証明しないといけない気がします。 自分の考えに間違いがあったら訂正をお願いします。 フェルマの小定理の証明方法について フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、(式a)から(式b)に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (a,m)=1のとき a^(φ(m))≡1 (mod m) 【フェルマの小定理】 a^(p-1)≡1 (mod p) ただし、aは正の整数(←条件を、少し制約しました。)、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 (式a) m=0 と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、 p-1 Σ((k)^m*(1)^m)≡1 (式b) 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 <証明終> 素数と組み合わせの問題 Z会の問題なのですが、わからないところがあるので質問します。 nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。 (1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。 (2)nと(2^n)-1は互いに素であることを示せ。 nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。 中国剰余定理について。 以下の画像についての証明をご教授願いたいです。すみません。n1とn2は互いに素ではありません。 論理的な誤りがあるなら指摘して いまnを3以上の自然数、mを自然数とする。 f(n)を「nと互いに素でnよりも小さい自然数の個数」と定義します。 f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、2、4、5の4個よりf(6) = 4です。 さてm<nのときにmとnが互いに素なら、n-mとnも互いに素です(これは証明されたとします) このときf(n)が偶数であることを証明します。 ------------ k∈Nとして n = 2k+1のとき {1、2・・k}の集合をA {k+1、k+2・・2k}の集合をBとする。集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+1≦ n-r ≦ 2kより互いに素なn-rは必ず集合Bに存在するので、集合Aの互いに素な個数とBの個数は同数なので、f(n)は偶数になる n = 2k+2のとき {1、2・・k}の集合をA {k+2、k+2・・2k+1}の集合をBとする。 {k+1}の集合をCとする 集合Cにおいて、n =2(k+1)とk+1は因数としてk+1(≧2)を持つので互いに素ではないのは 明らか。 集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+2≦ n-r ≦ 2k+1より互いに素なn-rは必ず集合Bに存在し、さきほどと同じ議論になるので、f(n)は偶数になる qed で何か誤りがあるかね? この定理の名前を教えてください aとpは互いに素とする aとpは共に整数とする pは素数とする このときに a^(p-1)≡1 (mod p)が成立 これは定理として名前がついているのですか? 証明は簡単にできました。 注目のQ&A 「You」や「I」が入った曲といえば? Part2 結婚について考えていない大学生の彼氏について 関東の方に聞きたいです 大阪万博について 駅の清涼飲料水自販機 不倫の慰謝料の請求について 新型コロナウイルスがもたらした功績について教えて 旧姓を使う理由。 回復メディアの保存方法 好きな人を諦める方法 小諸市(長野県)在住でスキーやスノボをする方の用具 カテゴリ 学問・教育 人文・社会科学 語学 自然科学 数学・算数 応用科学(農工医) 学校 受験・進学 留学 その他(学問・教育) カテゴリ一覧を見る OKWAVE コラム 突然のトラブル?プリンター・メール・LINE編 携帯料金を賢く見直す!格安SIMと端末選びのポイントは? 友達って必要?友情って何だろう 大震災時の現実とは?私たちができる備え 「結婚相談所は恥ずかしい」は時代遅れ!負け組の誤解と出会いの掴み方 あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど インターネット回線 プロバイダ、光回線など
お礼
ありがとうございます。 よくみたらpは素数ってかいてありました。