分組問題

引用：

WENDYCHI 寫道:
將1~100分成兩組
使得同組的數相乘除以101餘數為第一組的數
而不同組的數相乘除以101餘數為第二組的數

何謂第一組的數.第二組的數

目前找到一個廢話，1要在第一組數，否則其他數字與1相乘後除以101的餘數必不合條件。
而且1規定了以後就不用再管了，再來處理2~100就好了

開始暴力法了：以下的四十九個小組，每個小組裡的兩個數必須同時在同一個大組。(大組指的就是要拿來裝1~100的兩個組)
(2,51)(3,34)(4,76)(5,81)(6,17)
(7,29)(8,38)(9,45)(10,91)(11,46)
(12,59)(13,70)(14,65)(15,27)(16,19)
(18,73)(20,96)(21,77)(22,23)(24,80)
(25,97)(26,35)(28,83)(30,64)(31,88)
(32,60)(33,49)(36,87)(37,71)(39,57)
(40,48)(41,69)(42,89)(43,47)(44,62)
(50,99)(52,68)(53,61)(54,58)(55,90)
(56,92)(63,93)(66,75)(67,98)(72,94)
(74,86)(78,79)(82,85)(84,95)
這四十九個小組如果裡面的兩個數在不同大組裡的話，那麼1就得在第二大組，但1得在第一大組，不合。
另外2和3不可以同時在一個大組，否則一直推下去會推出矛盾。

我晚上無聊爆了一下，我得到了無解?!

有包括自乘嗎

引用：

WENDYCHI 寫道:
有

引用：

j2006mouse 寫道:
有包括自乘嗎

你問到重點了!

所以
可以從這101個餘數中的平方除以101的餘數
去推判第一組所該有的數…
是個艱難的任務
101不能分解，有點…

引用：

hansonyu123 寫道:

引用：

WENDYCHI 寫道:
有

引用：

j2006mouse 寫道:
有包括自乘嗎

你問到重點了!

所以
可以從這101個餘數中的平方除以101的餘數
去推判第一組所該有的數…
是個艱難的任務
101不能分解，有點…

第一組的前十個
1
4
9
16
25
36
49
64
81
100
之後就是
20
43
68
95
23
54
87
21
58
97
其實用等差級數去算也還好啦
不會很難
問題是重複到的…

引用：

hansonyu123 寫道:

引用：

hansonyu123 寫道:

引用：

WENDYCHI 寫道:
有

引用：

j2006mouse 寫道:
有包括自乘嗎

你問到重點了!

所以
可以從這101個餘數中的平方除以101的餘數
去推判第一組所該有的數…
是個艱難的任務
101不能分解，有點…

第一組的前十個
1
4
9
16
25
36
49
64
81
100
之後就是
20
43
68
95
23
54
87
21
58
97
其實用等差級數去算也還好啦
不會很難
問題是重複到的…

21 37
22 80
23 24
24 71
25 19
26 70
27 22
28 77
29 33
30 92
一大堆重複的

突然想到
只要試到50就好了
因為1^2跟100^2除以101的餘數相同
2^2和99^2也是如此
3^2、98^2
以此類推
最後一組是50^2、51^2
證明很簡單了

接上
如此一來，就會有50個餘數了(1~50)
但是有重複的，所以不能直接找出解

繼續暴力
31 52
32 14
33 79
34 45
35 13
36 84
37 56
38 30
39 6
40 85
41 65
42 47
43 31
44 17
45 5
46 96
47 88
48 82
49 78
50 76

引用：

WENDYCHI 寫道:
從上面拉下來我還以為你解了壘= =

引用：

hansonyu123 寫道:
接上
如此一來，就會有50個餘數了(1~50)
但是有重複的，所以不能直接找出解

快突破盲點吧 華生

啊！重複的怎麼辦！
啊啊啊
六年級就叫六聲吧
啊啊啊啊啊啊

引用：

WENDYCHI 寫道:
有

引用：

j2006mouse 寫道:
有包括自乘嗎

你問到重點了!

如果要算自乘的話，那我找完了，只不過還沒檢驗
第一組:1,4,5,6,9,13,14,16,17,19,20,21,22,23,24,25,30,31,33,36,37,43,45,47,49,52,54,56,58,64,65,68,70,71,76,77,78,79,80,81,82,84,85,87,88,92,95,96,97,100
第二組:2,3,7,8,10,11,12,15,18,26,27,28,29,32,34,35,38,39,40,41,42,44,46,48,50,51,53,55,57,59,60,61,62,63,66,67,69,72,73,74,75,83,86,89,90,91,93,94,98,99

引用：

justpoppingin 寫道:

引用：

WENDYCHI 寫道:
有

引用：

j2006mouse 寫道:
有包括自乘嗎

你問到重點了!

如果要算自乘的話，那我找完了，只不過還沒檢驗
第一組:1,4,5,6,9,13,14,16,17,19,20,21,22,23,24,25,30,31,33,36,37,43,45,47,49,52,54,56,58,64,65,68,70,71,76,77,78,79,80,81,82,84,85,87,88,92,95,96,97,100
第二組:2,3,7,8,10,11,12,15,18,26,27,28,29,32,34,35,38,39,40,41,42,44,46,48,50,51,53,55,57,59,60,61,62,63,66,67,69,72,73,74,75,83,86,89,90,91,93,94,98,99

怎麼來的！
我可憐的頭腦

突然發現
根本沒有重複
要換眼鏡了
第一組：
1,4,5,6,9,13,14,16,17,19,20,21,22,23,24,25,30,31,33,36,37,43,45,47,49,52,54,56,58,64,65,68,70,71,76,77,78,79,80,81,82,84,85,87,88,92,95,96,97,100
第二組：
2,3,7,8,10,11,12,15,18,26,27,28,29,32,34,35,38,39,40,41,42,44,46,48,50,51,53,55,57,59,60,61,62,63,66,67,69,72,73,74,75,83,86,89,90,91,93,94,98,99

呼…打完了

我是叫excel幫我模101啦...我懶得一個一個算，不過我真的很希望能寫一個程式，就只要給他一個數字，他就可以幫忙算出來，或告訴你不可能。
excel還有一個缺點，那就是他幫我模完後，我要自己整理結果= =
附註:我都打好了，你不必再慢慢打阿！

再加一題
是否所有大於1的奇質數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數

引用：

justpoppingin 寫道:
我是叫excel幫我模101啦...我懶得一個一個算，不過我真的很希望能寫一個程式，就只要給他一個數字，他就可以幫忙算出來，或告訴你不可能。
excel還有一個缺點，那就是他幫我模完後，我要自己整理結果= =
附註:我都打好了，你不必再慢慢打阿！

我剛剛才發現咩
我還以為有重複

引用：

hansonyu123 寫道:
再加一題
是否所有大於3的奇數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數

n=5時
(1，4)和(2，3)
n=7時
(1，2，4)和(3，5，6)

引用：

hansonyu123 寫道:

引用：

hansonyu123 寫道:
再加一題
是否所有大於3的奇數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數

n=5時
(1，4)和(2，3)
n=7時
(1，2，4)和(3，5，6)

n=9時
3^2除以9的餘數為0，故無解，命題為假
好快哦…

不然再加一個好了
n不為任一個小於n的自然數之平方的因數

n=11時
(1，3，4，5，9)
(2，6，7，8，10)

引用：

hansonyu123 寫道:
再加一題
是否所有大於3的奇數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數

嗯...
n=5---(1,4)(2,3)
n=7---(1,2,4)(3,5,6)
n=9會有問題，因為3^2和6^2都會被9除盡
看來要加一個條件：n為質數

引用：

justpoppingin 寫道:

引用：

hansonyu123 寫道:
再加一題
是否所有大於3的奇數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數

嗯...
n=5---(1,4)(2,3)
n=7---(1,2,4)(3,5,6)
n=9會有問題，因為3^2和6^2都會被9除盡
看來要加一個條件：n為質數

嗯嗯，我加吧

綜合

3 =>1 | 2
5=>1,4|2,3
7=>1,2,4|3,5,6
9=>無解
11=>1,3,4,5,9|2,6,7,8,10

引用：

hansonyu123 寫道:
再加一題
是否所有大於1的奇質數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數

再加一題
是否所有的質數n的2倍2n都可以找出兩組的數符合下列條件：
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數除了n之外

引用：

hansonyu123 寫道:

引用：

hansonyu123 寫道:
再加一題
是否所有大於1的奇質數n都可以找出兩組符合下列條件的數
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數

再加一題
是否所有的質數n的2倍2n都可以找出兩組的數符合下列條件：
1.兩組之間的數兩兩相異
2.各組數字的數量一樣
3.兩組數字數量之和為n-1
4.同一組內相乘(可自乘)除以n所得到的餘數皆屬於第一組的數
5.相異組的數相乘除以n所得到的餘數皆屬於第二組的數
6.任一個數都是小於n的自然數除了n之外

有了構想
只要証明：
(1)找出第一組的數後剩餘的數放進第二組後一定可以符合條件
(2)是否對於一個奇質數n，所有小於(n+1)/2的自然數之平方除以n的餘數兩兩相異？
(3)是否對於一個質數n，所有小於n的自然數之平方除以2n的餘數兩兩相異？

(2)和(3)差不多證明出來了，不曉得對不對…

(2)
設兩自然數a，b(a<b)之平方除以n的餘數相同，且a，b皆小於(n+1)/2
那麼a^2≡b^2(mod n)
也就是說a^2+cn=b^2，其中c是整數
又因為a，b皆小於(n+1)/2，所以c一定小於n
設a=p^2-q^2
根號(cn)=2pq
b=p^2+q^2
其中p和q皆為整數
則cn=4(pq)^2
因為n是質數，所以p和q其中一個為n
設p為n
則c=4nq^2
因為c<n
所以q=0
c=0，所以a^2=b^2
又因為a不等於b
所以a=-b，兩者一定至少有一個不為自然數，矛盾。
所以不存在這樣子的a和b，命題得證
(3)類似2，不過將cn改成2cn

不曉得這樣子證對不對
如果對了，那還差(1)

引用：

WENDYCHI 寫道:

引用：

hansonyu123 寫道:
(2)
設兩自然數a，b(b>a)之平方除以n的餘數相同，且a，b皆小於(n+1)/2
那麼a^2≡b^2(mod n)
也就是說a^2+cn=b^2，其中c是整數
又因為a，b皆小於(n+1)/2，所以c一定小於n
設a=p^2-q^2
根號(cn)=2pq
b=p^2+q^2
其中p和q皆為整數
則cn=4(pq)^2
因為n是質數，所以p和q其中一個為n
設p為n
則c=4nq^2
因為n>c
所以q=0
c=0，所以a^2=b^2
又因為a不等於b
所以a=-b，兩者一定至少有一個不為自然數，矛盾。
所以不存在這樣子的a和b，命題得證
(3)類似2，不過將cn改成2cn

不曉得這樣子證對不對
如果對了，那還差(1)

你的文字被吃掉了

只要知道二次剩餘和完全剩餘 這有甚麼難的= =

可是我不知道那是什麼
解釋一下吧~~~

引用：

WENDYCHI 寫道:

引用：

hansonyu123 寫道:
(2)
設兩自然數a，b(b>a)之平方除以n的餘數相同，且a，b皆小於(n+1)/2
那麼a^2≡b^2(mod n)
也就是說a^2+cn=b^2，其中c是整數
又因為a，b皆小於(n+1)/2，所以c一定小於n
設a=p^2-q^2
根號(cn)=2pq
b=p^2+q^2
其中p和q皆為整數
則cn=4(pq)^2
因為n是質數，所以p和q其中一個為n
設p為n
則c=4nq^2
因為n>c
所以q=0
c=0，所以a^2=b^2
又因為a不等於b
所以a=-b，兩者一定至少有一個不為自然數，矛盾。
所以不存在這樣子的a和b，命題得證
(3)類似2，不過將cn改成2cn

不曉得這樣子證對不對
如果對了，那還差(1)

你的文字被吃掉了

只要知道二次剩餘和完全剩餘 這有甚麼難的= =

那(1)呢？
可以用那些什麼定理證嗎？
我只是個可愛的六年級(被毆)

引用：

WENDYCHI 寫道:

引用：

hansonyu123 寫道:

引用：

WENDYCHI 寫道:

引用：

hansonyu123 寫道:
(2)
設兩自然數a，b(b>a)之平方除以n的餘數相同，且a，b皆小於(n+1)/2
那麼a^2≡b^2(mod n)
也就是說a^2+cn=b^2，其中c是整數
又因為a，b皆小於(n+1)/2，所以c一定小於n
設a=p^2-q^2
根號(cn)=2pq
b=p^2+q^2
其中p和q皆為整數
則cn=4(pq)^2
因為n是質數，所以p和q其中一個為n
設p為n
則c=4nq^2
因為n>c
所以q=0
c=0，所以a^2=b^2
又因為a不等於b
所以a=-b，兩者一定至少有一個不為自然數，矛盾。
所以不存在這樣子的a和b，命題得證
(3)類似2，不過將cn改成2cn

不曉得這樣子證對不對
如果對了，那還差(1)

你的文字被吃掉了

只要知道二次剩餘和完全剩餘 這有甚麼難的= =

可是我不知道那是什麼
解釋一下吧~~~

http://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E5%89%A9%E4%BD%99#.E8.B4.A8.E6.95.B0.E4.BA.8C.E6.AC.A1.E5.89.A9.E4.BD.99
維基百科

看完了
那個歐拉準則…看到那些次方就看不下去了