- 締切済み
合同式の問題の証明を教えて下さい。
gcd(b,561)=1であれば b^560≡1(mod 3) b^560≡1(mod 11) b^560≡1(mod 17) が成り立つことを証明せよ。 ヒント： pが素数でbを割り切らなければ b^(p-1)≡(mod p) が成り立つ。 という問題なのですが分かりやすく証明を教えていただけないでしょうか？
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
関連するQ&A
- 最大公約数 gcd(a,b,c) と一次合同式の解の存在
初等整数の証明で困ってます。 (1)gcd(a,b,c)はgcd(a,b)の約数であることを証明せよ。 (2)gcd(gcd(a,b),c)はgcd(a,b,c)の倍数であることを証明せよ。 また合同式の定理の証明について gcd(a,b)=1ならばax≡c(mod b)は解をもつ。 さらにこの合同方程式の一つの解をpとすると、すべての整数kについてp+kb も解である。逆にこの合同方程式の任意の解はp+kb と表わされる。 ax≡c(mod b) は b | (ax-b) を導けばよいのでしょうか？ お願いします。
- 締切済み
- 数学・算数
- 合同式に関する問題です
学校で出た下のような問題が解けないのですがよろしくお願いします。 aは自然数であり、ｐ＝a*a+1 は素数であるとする。この時ｎ*ｎ+1がｐの倍数であるということとn≡a(mod p) もしくは n≡p-a(mod p) であることは同値である事を示せ。 という問題です。 中二にも分かるレベルで教えていただけると嬉しいです。
- ベストアンサー
- 数学・算数
- 合同式
(1)43x+56y=10を満たす整数x,yを求めよ。 (2)あるイベントで1ケース24本入りの缶を何ケースか開けて、1人7本ずつ分けたところ、1本残った。参加予定人数は25人であるとすると、参加したのは何人か。 という問題なのですが、 (1)43x=-56y+10 43x≡10(mod 56) (2)ケースの数をx、参加した人数をyとすると、 24x=7y+1…(1) 24x≡7y+1(mod 7) 24x≡6(mod 7) 4x≡1(mod 7) gcd(4,7)=1 x=5 (1)に代入して、y=17 よって、答えは17人。 (1)は、この後の計算の仕方はネットでも調べてみたのですが、いまいち、分からず困っています。(2)の方は、この計算方法で合っているでしょうか？他にもやり方はあるんでしょうか？ アドバイスやヒントなど、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 合同式の証明について
自分の使っている参考書に書かれている合同式の証明で a≡c (mod m) b≡d (mod m)より a-c=mp b-d=mq (p,qは整数)とおくことが出来る。 よって (a+b)-(c+d)=(a-c)+(b-d)=mp+mq=m(p+q) (a-b)-(c-d)=(a-c)-(b-d)=mp-mq=m(p-q) ab-cd=(c+mp)(d+mq)-cd=m(cq+pd+mpq) ゆえに(a+b)-(c+d),(a-b)-(c-d),ab-cdはmの倍数であるから a+b≡c+d(mod m) a-b≡c-d(mod m) ab≡cd(mod m) は成り立つ。 と書かれているのですが、全体的によく理解が出来ません。 まず なぜ a≡c (mod m) b≡d (mod m) であれば a-c=mp b-d=mq (p,qは整数)と、おくことが出来るのかということと ab-cdからどのような計算をすると(c+mp)(d+mq)-cd このようになるのかもわかりません。 数学はあまり得意ではないので中学生レベルの学力でも理解できるように 説明していただけると有り難いです。
- ベストアンサー
- 数学・算数
- 大学数学で、合同方程式の問題なんですが、
大学数学で、合同方程式の問題なんですが、 ｘ＾９７≡２２ ｍｏｄ ２２５ の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとｘ＾ｔ≡ａ ｍｏｄ ｎ の解を求める際に ｇｃｄ（ａ，ｍ）＝１ ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。 このときのａ，ｍ，ｋは一般自然数です ｘ＾９７は指数でｘの９７乗のことです よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- modに関する証明問題
pをp≡3mod4を満たす素数として、a≡b^2mod pが解を持つとしたとき a^(p+1)/4 が a の mod p での平方根になる ことを示したいのですが、どうしてそうなるのか、さっぱりです。 どなたか教えていただけないでしょうか。
- ベストアンサー
- 数学・算数
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 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)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- 素因数分解の証明問題
素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、 φ(n)=n｛1-(1/p_1)｝｛1-(1/p_2)｝・・・｛1-(1/p_r)｝となることを示せ。 ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 倍数の問題
次の問題は小学校５・６年の参考書に載ってあったのですが、この問題を見て疑問に思ったことがあります。 【問題】１２，１８のどちらで割っても３余る数のうち、最も小さい整数を求めなさい。 この問題は、どちらで割っても余りが同じになるので、最小公倍数をｇｃｄ（ａ，ｂ）で表すとすると、 ｇｃｄ（１２，１８）＋３＝３９ で解けるのですが、 （割ると３余るということは、割られる数は割る数の倍数より３大きいということになるから。） 余る数が違ったらどうやって解くんだ！！という疑問が生まれてしまいました。 問題にしてみると、次のようになります。 【問題】ａで割ると余りがｐになり，ｂで割ると余りがｑになる数のうち、ｎ番目の整数を求めよ。 ただし、最小公倍数をｇｃｄ（ａ，ｂ）で表すものとする。 条件を満たす整数を１番目に限定しないようにしました。 これがｐ＝ｑ＝ｒなら、ｇｃｄ（ａ，ｂ）ｎ＋ｒで簡単に求められるのですが、上のように余りが異なる場合はどうやって求めれば良いのでしょうか？
- ベストアンサー
- 数学・算数
お礼
あー、、、ごめんなさい。 完全に勘違いしてました・・・。。 ありがとうございます。 とてもたすかりました。