- ベストアンサー
合同法について
a, bを自然数とする。(a,b)=1 （aとbの最大公約数が1) のとき、a^n=1 mod b をみたす 自然数nが存在することを示せ。 わかりません。。教えてください！
- smileshower
- お礼率0% (0/28)
- 数学・算数
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
http://aozoragakuen.sakura.ne.jp/suuron/node32.html の定理 23(オイラーの定理)を使ってよいなら オイラーの定理より、a^{φ(b)}≡1 (mod b)がいえる。 φ(b)が求める整数nである。 ・・・・・・・・・・・・・・・証明終わり・・・・・・・・・・・・ 余りにもあっけないのでオイラーの定理を使わない場合も b+1個の整数1(=a^0),a,a^2,…,a^bを考える。 bで割ったときの余りは0,1,…b-1だからb通りの値が考えられる。 したがってb+1個の数1(=a^0),a,a^2,…,a^bの中にはbで割ったときの余りが等しくなる2数が必ず存在する。 それをa^i,a^jとする(ただし、i,jは0≦i＜j≦bをみたす整数) このとき、a^j-a^i=a^i{a^(j-i)-1}はbで割り切れる。 a,bは互いに素だからa^iとbも互いに素である。 したがってa^(j-i)-1がbで割り切れることがわかる よって、a^(j-i)≡1 (mod b)がいえる。j-iが求める整数nである。
関連するQ&A
- 線形合同式と数列周期
a,b,kを a≡1(mod4)、bと2との最大公約数が1、k>=2 を満たす自然数とすると、 線形合同式 x_(n+1)≡a*(x_n)+b mod 2^k ただし 0<= (x_n) <2^k で定義される0から(2^k)-1の間の整数による数列{x_n} は、任意の初期値x_0 に対して 周期が2^kであることを示せ。 わかりません。。よろしくお願いします！！
- ベストアンサー
- 数学・算数
- 未知数があるとき ユークリッド互助法 適用 方法
問題 8n+4と7n+1の最大公約数が5になるような100以下の自然数nはいくつあるか？ 解答 ユークリッドの互助法を使う 8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数＝n+3と20の最大公約数 さらに……… という問題と解答なのですが、疑問があります （以下 自然数～ を 自～ と表記します） ユークリッドの互助法とは 自aと自bの最大公約数＝ (自a＝自b×自c＋自d ∧ 0≦自d＜自b ⇔ 自b＝～ ∧ 自d＝～)で定まる自dの値 と 自b の最大公約数 が成り立つという事実を使って2数の最大公約数を、より簡単な2数の最大公約数に還元し もとめる方法ですよね？ そうなるとこの場合にどのように適用していいのかわかりません。 8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数 の部分は 8n+4＝(7n+1)×自c＋自d ∧ 0≦自d＜7n+1 ⇔ 自ｃ＝1 ∧ 自ｄ＝n+3 で自dが一通りに定まるのがわかるのですが 7n+1とn+3の最大公約数＝n+3と20の最大公約数 の部分は 7n＋1＝(n+3)×自d+自d ∧ 0≦自d＜n+3 ⇔ 自c＝ ∧ 自d＝ となるので 自ｃが7以下であることはわかりますが、自cは1.2.3.4.5.6のどれでもokですよね そうすると自ｄが一通りに定まらず、どうやっていいのかわかりません
- ベストアンサー
- 数学・算数
- ユークリッドの互除法で最大公約数を求める
＜問題＞ n^2+2n+1とn+3の最大公約数になりうる値をすべて求めよ ＜解答＞ 整数a,bに対してa,bの最大公約数をg(a,b)とあらわす。 g(n^2+2n+1,n+3)=g(n+3,4) 4の正の約数は1,2,4であるから、g(n+3,4)として考えうるのも1,2,4である。 例えば、 n+3=5 すなわちn=2のとき、g(5,4)=1 n+3=6 ・・・ g(6,4)=2 n+3=8 ・・・ g(8,4)=4 となり、最大公約数として可能な数は1,2,4の３つの自然数である。 ＜質問＞ 「g(n+3,4)として考えうるのも1,2,4である。」 が必要条件であることはわかります。 その後、解答でなにがしたいのかよくわかりません。 なぜ例示しただけで「最大公約数として可能な数は1,2,4の３つの自然数である。」といえるのでしょうか？ よろしくお願いします。 ＜思ったこと＞ 必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、「4の正の約数は1,2,4である」であることを示すことになると思います。
- ベストアンサー
- 数学・算数
- nが素数であるかどうかの判定
素数判定の勉強をしています。 次の文の内容が成立する理由がわかりませんでした。 -----内容----- n-1 = 2^(t-1) * m としたとき とある整数a (aは2以上n-2以下)において もし a^{(2^j)*m} ≡ 1 mod n かつ a^［{(2^(j-1)}*m] ≠ ±1 mod n ならば a^［{(2^(j-1)}*m] -1 と nの自明でない最大公約数がみつかりnは素数ではないと判断できる。 (ここで、jは1以上t-1以下の自然数。また記号「≠」を「not 合同」の意味で使用しています。) -----終了----- これはなぜなのでしょうか？ なぜ公約数が見つかるのでしょうか？ アドバイスよろしくお願いします。
- ベストアンサー
- 数学・算数
- 合同式に関する問題です
学校で出た下のような問題が解けないのですがよろしくお願いします。 aは自然数であり、ｐ＝a*a+1 は素数であるとする。この時ｎ*ｎ+1がｐの倍数であるということとn≡a(mod p) もしくは n≡p-a(mod p) であることは同値である事を示せ。 という問題です。 中二にも分かるレベルで教えていただけると嬉しいです。
- ベストアンサー
- 数学・算数
- 証明の仕方を教えてください。
pを自然数とし、二次方程式x^2-px-1=0の二つの解をα、βとする。 数列{a(n)}をan=α^(n-1)+β^(n-1) (n=1,2,3…)によって定める。 （１）すべての自然数ｎに対し、a(n+2)=pa(n+1)+a(n)が成り立つことを示せ。 （２）すべての自然数ｎに対し、a(n)は自然数であることを示せ。 （３）pが奇数であるとき、すべての自然数ｎに対し、a(n)とa(n+1)の最大公約数は１であることを示せ。 という問題です。 （１）は計算して解けたのですが、（２）（３）をどのように証明したらよいのか分かりません。 教えていただけないでしょうか。よろしくお願いします。
- ベストアンサー
- 数学・算数
- n＾2+3n+8とn+2の最大公約数
高校数学の問題です 「nは自然数とする。n＾2+3n+8とn+2の最大公約数として考えられる数を全てもとめよ」 この問題の解き方をどなたか教えてください。
- ベストアンサー
- 数学・算数
- 自然数と偶数の一対一対応について
自然数の中から小さい方から順番にn個取り出した集合をAとし、 正の偶数の中から小さい方から同様に、同じ数だけ取り出した集合をBとします (要は自然数と正の偶数の一対一対応です) A={1,2,3,4,5, ...n} B={2,4,6,8,10,...2n} (AとBは同じ数) ここで、あるnの時の"Aには存在しないBの要素(値)の数"を考えます n=1の時、1個 n=2の時、1個 n=3の時、2個 個数だけ上げていくと、 1,1,2,2,3,3,4,4,5,5,.....と続きます "Aには存在しないBの要素の数"は、nの数に対して単調増加しており、 全てのnにおいて、少なくとも1以上であるように見えます また、nが無限大になった時でも、"Aには存在しないBの要素の数"は1以上あるようにしか思えません nが無限の時、Aを自然数全体の集合、Bを正の偶数全体の集合と呼ぶとします。 nが無限の時でも、Aに含まれないBの要素が存在します。 言い換えれば、自然数(=A)ではない正の偶数が存在するということです。 (もしそうなら最大値の存在が示せそうな気がしますし、現時点で私はそれが正しいように思います) この考えで、どこか間違いがあれば教えてください
- 締切済み
- 数学・算数
補足
はい！お願いします。