19509：再アップ問...その2...^^

問題19509(鍵コメT様からの提示問 https://blogs.yahoo.co.jp/crazy_tombo/50304328.html)

a,b,c,dは自然数で，cとdは互いに素，かつc>dであるとする．
1以上abcd以下の整数のうち，
acで割った余りがadで割った余りよりも小さいものはいくつあるか．

解答

・鍵コメT様からの想定解頂戴 Orz〜

ある自然数nをaで割った余りをx，商をyとします．
nをacで割った余りは，a*(yをcで割った余り)+xであり，
nをadで割った余りは，a*(yをdで割った余り)+xだから，
「nをacで割った余りがnをadで割った余りよりも小さい」ための条件は，
「yをcで割った余りr1がyをdで割った余りr2よりも小さい」(*)ことです．

c,dは互いに素であることから，
0≦r1<c,0≦r2<dを満たす任意の整数r1,r2の組合せに対して
yをcdで割った余りが1つ定まりますが，
(*)から，条件を満たすr1,r2の組合せは，
0≦r1<r2<dを満たすdC2=d(d-1)/2(通り)だけあり，
結局，yをcdで割った余りはd(d-1)/2通り可能です．

0≦y<bcdだから，可能なyはbd(d-1)/2通り，xがa通りより，
求める個数は「abd(d-1)/2個」となります．

本問は問題17338の再掲で，問題17335(https://blogs.yahoo.co.jp/crazy_tombo/50304159.html)の一般化として提示したものであり，

問題17335に当てはめれば「4*25*4*3/2=600(個)」とできることになります． 

*熟読玩味ぃ〜^^;v

・鍵コメT様からの詳しい解説頂戴〜m(_ _)m〜♪

互いに素である2数c,dについて，
nをcで割った余りとnをdで割った余りが指定されたとき，
n≡r1 (mod c)とn≡r2 (mod d)が条件であり，
dn=dr1 (mod cd)…[1]かつ cn≡cr2 (mod cd)…[2]となります．
[2]から[1]を，左辺のnの係数が正である限り引いていくと，
左辺のnの係数は最終的にはdより小さくなります．
次に[1]と[3]について同様にして[4]を得，[3]と[4]について同様にして…
と繰り返していくと，左辺のnの係数は，
ユークリッドの互除法を実行しているのと同じことになり減っていき，
c,dが互いに素だから，最終的には1になります．
つまり，n≡○ (mod cd)
のような式が手に入ります．(「中国の剰余定理」と言われる定理です．)

つまり，yをcで割った余りr1とyをdで割った余りr2が定まれば，
yをcdで割った余りが定まることになりますし，
逆に，yをcdで割った余りが定まれば，
yをcやdで割った余りが定まることは明らかだと思います．

すると，yの満たすべき条件
「cで割った余りr1がdで割った余りr2よりも小さい」，
つまり
「(r1,r2)=(0,1),(0,2),…,(0,d-1),
(1,2),(1,3),…,(1,d-1),
(2,3),(2,4),…,(2,d-1),
…,
(d-3,d-2),(d-3,d-1),
(d-2,d-1)」
は，(r1,r2)として
0〜d-1のd個から2個を選ぶ選び方dC2通りだけあることがわかります．

*ありがたいことに...半分くらいわかったり ^^;v Orz〜

[スモークマン]

＞10:48pmの鍵コメT様へ ^^
解答提示グラッチェでっす ^^v
>0≦r1<c,0≦r2<dを満たす任意の整数r1,r2の組合せに対して
yをcdで割った余りが1つ定まりますが，
(*)から，条件を満たすr1,r2の組合せは，
0≦r1<r2<dを満たすdC2=d(d-1)/2(通り)だけあり，

の部分がわたしにはすぐにわかりませんけど...^^;
アップさせていただきまっす〜m(_ _)m〜v

[スモークマン]

↑
なお...間違ったリンク先は訂正させていただきました ^^; Orz〜

[スモークマン]

＞1:40amの鍵コメT様へ ^^
解説グラッチェ〜♪
アバウトには、cdで割ったときの余りの中には、後半のような題意を満たす余りの組み合わせが必ず存在するから...c(d,2)通りあり、
abcdの中なら...そのab倍個になる...と理解できました ^^;v
追記させていただきまっす〜m(_ _)m〜