【最大10000ポイント】当たる!!質問投稿キャンペーン!

式 ( 13 * d ) % 176 = 1
この時、d=の求め方を教えて下さい!

答えは複数あると思うんですが、解き方が知りたいです。

このQ&Aに関連する最新のQ&A

A 回答 (6件)

>>13d+176x=1を満たす整数dを探せばいい.


>この経緯から理解できていません。説明頂けると助かります。

え・・だってこれって「問題文そのもの」でしょ
式の意味が分かってないのですか?

>式 ( 13 * d ) % 176 = 1
>この時、d=の求め方を教えて下さい!

ってのは,「13dを176で割って余り1」ってことだから
商をrとおけば
13d=176r+1
13d-176r=1

-rをxと置き換えれば
13d+176x=1

どうしてこの形にするのかといえば

ユークリッドの互除法:
aとbが互いに素のとき
ax+by=1となる整数xとyが存在する

の形のそろえるだけの意味.
この定理があるから問題の式でdは解を持つことが分かるし
この定理を使って解を導くのがこの手の「合同方程式」の一番簡単なパターン.

このタイプの合同方程式は何はともあれ
一個でも解を導けば芋づる式ででてくる

13d+176x=1
まずは176を13で割ってみると
176=13*13+7でしょ
だから
13d+(13*13+7)x=1
13(d+13x)+7x=1
よくみれば2*7=14だから
13*(-1)+7*2=1でしょ
だから
一個だけ解がほしければ
d+13x=-1
x=2
よってd=-27ってのが答えの「一個」になる
実際
13*(-27)=-351=176*(-2)+1

d=-27って答えがわかれば
13d+176x=1
ってのは一次関数だし,13と176ってのが互いに素なんだから
-27に176の倍数を加えても解だし
それしか解がないことがわかる(直線の13d+176x=1のグラフを(d,x)平面で考えてみればいい)

だから
d=-27+176k(kは整数)となる
けど,「余り」になる部分が-27ってのはあんまりよくないから
176を加えて
d=149+176k
#なんでかといえば,176で割った余りは0以上176未満にしておくほうが
#普通の「剰余の式」に合致しているから

この回答への補足

>ユークリッドの互除法:
>aとbが互いに素のとき
>ax+by=1となる整数xとyが存在する

分からなかったのはこの部分です。定理を知らなかったので、どうしてそうするのかが疑問でした。
定理は別途調べて見たいと思います。求め方は理解はできました。

有難うございました。

補足日時:2010/11/28 22:12
    • good
    • 0

「*」は掛け算「×」のこと、「%」は整数の割り算の余りを求める演算記号です。


だから、質問は、
( 13 * d ) % 176 = 1 ・・・・(1)
は、dを13倍したものを176で割ると余りが1になる。dはいくつか?
という問題。
a,b,cはみんな整数とする。dももちろん整数です。

同じようなことを何回か繰り返しますよ。

1.
(1)式を書き換えれば、
13d/176=a 余り1
ということだから、
13d=176a+1
です。
だから、
d=(176a+1)/13=13a+(7a+1)/13
です。
dは整数だから、(7a+1)/13も整数です。

2.
で、
(7a+1)/13=b
とします。
すると、
7a+1=13b
だから、
a=(13b-1)/7=b+(6b-1)/7
になります。
aは整数だから、(6b-1)/7 も整数です。

3.
で、
(6b-1)/7=c
とします。
すると、
6b-1=7c
で、
b=(7c+1)/6=c+(c+1)/6
です。
bは整数だから、(c+1)/6 も整数です。

4.
ということは、c+1が6の倍数ということです。
要するにc+1は、6,12,18,・・・だから、
cは、5,11,17・・・ということです。
5
.
ここから、逆にたどって
c=5なら、b=6、a=11
になりますね。

6.
a=11なら、d=149です。

7.
まとめると、
  c     b     a     d
  5     6     11    149 
  11    13    24    325
  17          37    501
  ・          50    677
  ・                853
  ・
176ずつ増えるだけだな。

丁寧にやると以上のようになるが、他の回答者が書かれているくらいで答えは出る。

この回答への補足

ご丁寧にありがとうございます。

補足日時:2010/11/28 22:18
    • good
    • 0

>>176a+1=13.*13a+7a+1だから、7a+1が13の倍数となればよい。


13.となっているのは、打ち間違いです。13*13aが正しい。
13*13aとしたのは、13の倍数であることを示すため。すると、あと7a+1が13の倍数なら、176a+1は13の倍数となるわけです。

この回答への補足

ありがとうございます。

補足日時:2010/11/28 18:19
    • good
    • 0

dは「176で割って余り149の整数」全部



13d+176x=1を満たす整数dを探せばいい.
13*(-27)+176*2=1より
13(d+27)+176(x-2)=0
13と176は互いに素だから
d+27は176の倍数
よって
d+27=176kと表せる
つまり
d%176=-27
だから
d%176=176-27=149

この回答への補足

すいません、考えたのですが最初から理解できませんでした。

>13d+176x=1を満たす整数dを探せばいい.
この経緯から理解できていません。説明頂けると助かります。

補足日時:2010/11/28 17:14
    • good
    • 0

(13*d)を176で割った商をaとする。

(ただしaは整数。)
すると、13*d = 176a+1 となる。
つまりd = (176a+1)/13です。
あとはaに適当な数(123、0、-10など)を当てはめて計算してみましょう。

一例 a=0とする。
d = (176*0+1)/13 = 1/13

この回答への補足

ありがとうございます。

補足日時:2010/11/28 17:01
    • good
    • 0

( 13 * d )を 176 で割ったときの商をaとすると、


( 13 * d ) =176 a+1
176a+1が13の倍数になるときを考えればよい。
すなわち、
176a+1=13.*13a+7a+1だから、7a+1が13の倍数となればよい。
あとは、逆算すれば?

この回答への補足

ご回答ありがとうございます。

>176a+1=13.*13a+7a+1だから、7a+1が13の倍数となればよい。
この式176a+1=13.*13a+7a+1について理解できませんでした。

部分的に.*というのはなんでしょうか。
また、13.*13a+7a+1の解説をお願いしたいです。

補足日時:2010/11/28 17:01
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング