合同式

質問

(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)の方は、この計算方法で合っているでしょうか？他にもやり方はあるんでしょうか？

アドバイスやヒントなど、よろしくお願いします。

回答No.1

take_5 · ベストアンサー

そんじゃ、（1）を。。。。。。。

＞43x+56y＝10‥‥(1)　を満たす整数x,yを求めよ。

これは不定方程式という。フェルマーの小定理と関係がある。

(1)を満たすxとyの特別解を各々α、βとすると、43α＋56β＝10‥‥(2)
(1)－(2)より　43（x－α）＝56（β－y）。
43と56は互いに素から、mを整数として、x－α＝56m、β-y＝43m‥‥(3)であるから、
αとβの具体値を1つ求めると（α、β）＝（-18、14）‥‥(4)
従って、(3)と(4)から、x＝56m-18、y＝14－43m（m：整数）。

この不定方程式が面倒なところは、(4)を求めるところにある。
しかし、それもより簡単な不定方程式に還元していく事により解決できる。

（2）も同様に解ける。この場合の特別解は質問者がもとめている通り（α、β）＝（5、17）。
これは、xとyの係数が小さいから上に、自然数という条件があるので求め易い。

補足

回答ありがとうございます。
(1)ですが、take_5さんのやり方は理解できました。
これを合同式、modなどを使うとどう表すことができるのでしょうか？
よろしかったら、そちらも教えていただけると嬉しいです。
よろしくお願いします。

回答No.3

take_5

＞これを合同式、modなどを使うとどう表すことができるのでしょうか？
＞(1)は、この後の計算の仕方はネットでも調べてみたのですが、いまいち、分からず困っています

合同式は、確かに時により大きな力になるが、係数が大きいとその威力も激減する。
従って、この問題にも余り有効ではないように思うが、どうしても合同式というのなら。。。。。。笑

私が、最初の回答で
＞この不定方程式が面倒なところは、(4)を求めるところにある。
＞しかし、それもより簡単な不定方程式に還元していく事により解決できる。

と、書いたがそこにヒントがあるように思う。後は、自分で考え、答案として纏めると良い。しかし、面倒そう。。。。笑。

＞(1)43x+56y＝10を満たす整数x,yを求めよ。

43*（x+y）＋13y＝10と変形できるから、x+y＝m　‥‥(1)より43m＋13y＝10。続いて、13（y+3m）＋4m＝10と変形して、
y+3m＝k　‥‥(2)とすると、13k＋4m＝10より4（m＋3k）＋k＝10と変形して、m＋3k＝n　‥‥(3)とすると、
4n＋k＝10であるから、（n、k）＝（2、2）‥‥(4)　(3)と(4)から、m＝-4.　従って、(2)よりy＝14.　(1)よりx＝-18.

合同式を考えるなら、最後の4n＋k＝10から、謂わば“上向”していくことになるが、私はとてもやる気がしない。。。。面倒そうなんで。

やはり、不定方程式を使うのがｂｅｔｔｅｒと思うんだが？
この問題から離れても、（2）でやったような解法は覚えておいた方が良い。

お礼

回答ありがとうございます。
確かに、合同式でやると、面倒みたいですね。

丁寧な説明、ありがとうございました。

回答No.2

take_5

（2）の解をこの問題に即して解説を。。。。。笑

24x＝7y+1から、y＝3x＋（3x－1）/7.‥‥(1)
yは自然数で　y≦25（その予定人数に合わせて缶を用意しているはずなので、そう解釈しても良いだろう）
という条件から、条件：24x＝7y+1より24x-1≦175.即ち、x≦7‥‥(2)である。
ところが(1)より、3x－1は7の倍数から、3x－1＝7、14、21、28、35、‥‥‥であるが、(2)を満たすものは、x＝5。
この時、y＝17.

お礼

アドバイスありがとうございます。
(2)合っているようで、よかったです。
take_5さんのようなやり方もあるのですね。参考になりました。
解説、ありがとうございました。