一、程式碼
題目： 121x≡1 mod 1002
#include <iostream>
#include <math.h>
using namespace std;
void main()
{
int n1,n2,n3,temp1,temp2,temp3,x,N;
int a=0,b=1; //設定變數值
n1=1002,n2=121;
n3=1;
N=n1;
while (n1%n2)
{
temp1=n1%n2; //將所得餘數存到temp1值
temp2=n2-temp1;
if(temp2<temp1)
{
x=floor((double)n1/n2);
x=(int)x+1;
temp3=(b*x)-a;
a=b;
b=temp3;
n1=n2;
n2=temp2;
}
else
{
x=floor((double)n1/n2);
temp3=a-(b*x);
a=b;
b=temp3;
n1=n2;
n2=temp1;
}
if(n2==1)
{
if(b<0)b=b+N;
b=b*n3;
if(b>N)b=b%N;
cout<<"x= "<<b<<endl;
break;
}
}
system("pause");
}二、結果
(1) 121x≡1 mod 1002之結果
X=265
(2) 建立N =3~20 的表格
N=3
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
|||||||||||||||||||||||||||||||||||
x
|
2
|
|||||||||||||||||||||||||||||||||||
N=4
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
||||||||||||||||||||||||||||||||||
x
|
無解
|
3
|
||||||||||||||||||||||||||||||||||
N=5
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
|||||||||||||||||||||||||||||||||
x
|
3
|
2
|
4
|
|||||||||||||||||||||||||||||||||
N=6
|
||||||||||||||||||||||||||||||||||||
a
|
2、3、4
|
5
|
||||||||||||||||||||||||||||||||||
x
|
無解
|
5
|
||||||||||||||||||||||||||||||||||
N=7
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
5
|
6
|
|||||||||||||||||||||||||||||||
x
|
4
|
5
|
2
|
3
|
6
|
|||||||||||||||||||||||||||||||
N=8
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、6
|
3
|
5
|
7
|
||||||||||||||||||||||||||||||||
x
|
無解
|
3
|
5
|
7
|
||||||||||||||||||||||||||||||||
N=9
|
||||||||||||||||||||||||||||||||||||
a
|
3、6
|
2
|
4
|
5
|
7
|
8
|
||||||||||||||||||||||||||||||
x
|
無解
|
5
|
7
|
2
|
4
|
8
|
||||||||||||||||||||||||||||||
N=10
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、5、6、8
|
3
|
7
|
9
|
||||||||||||||||||||||||||||||||
x
|
無解
|
7
|
3
|
9
|
||||||||||||||||||||||||||||||||
N=11
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|||||||||||||||||||||||||||
x
|
6
|
4
|
3
|
9
|
2
|
8
|
7
|
5
|
10
|
|||||||||||||||||||||||||||
N=12
|
||||||||||||||||||||||||||||||||||||
a
|
2、3、4、6、8、9、10
|
5
|
7
|
11
|
||||||||||||||||||||||||||||||||
x
|
無解
|
5
|
7
|
11
|
||||||||||||||||||||||||||||||||
N=13
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|||||||||||||||||||||||||
x
|
7
|
9
|
10
|
8
|
11
|
2
|
5
|
3
|
4
|
6
|
12
|
|||||||||||||||||||||||||
N=14
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、6、7、8、10、12
|
3
|
5
|
9
|
11
|
13
|
||||||||||||||||||||||||||||||
x
|
無解
|
5
|
3
|
11
|
9
|
13
|
||||||||||||||||||||||||||||||
N=15
|
||||||||||||||||||||||||||||||||||||
a
|
3、5、6、9、10、12
|
2
|
4
|
7
|
8
|
11
|
13
|
14
|
||||||||||||||||||||||||||||
x
|
無解
|
8
|
4
|
13
|
2
|
11
|
7
|
14
|
||||||||||||||||||||||||||||
N=16
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、6、8、10、12、14
|
3
|
5
|
7
|
9
|
11
|
13
|
15
|
||||||||||||||||||||||||||||
x
|
無解
|
11
|
13
|
7
|
9
|
3
|
5
|
15
|
||||||||||||||||||||||||||||
N=17
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|||||||||||||||||||||||||
x
|
9
|
6
|
13
|
7
|
3
|
5
|
15
|
2
|
12
|
14
|
10
|
|||||||||||||||||||||||||
a
|
13
|
14
|
15
|
16
|
||||||||||||||||||||||||||||||||
x
|
4
|
11
|
8
|
16
|
||||||||||||||||||||||||||||||||
N=18
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、6、8、10、12、14、3
9、15、16
|
5
|
7
|
11
|
13
|
17
|
||||||||||||||||||||||||||||||
x
|
無解
|
11
|
13
|
5
|
7
|
17
|
||||||||||||||||||||||||||||||
N=19
|
||||||||||||||||||||||||||||||||||||
a
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|||||||||||||||||||||||||
x
|
10
|
13
|
5
|
4
|
16
|
11
|
12
|
17
|
2
|
7
|
8
|
|||||||||||||||||||||||||
a
|
13
|
14
|
15
|
16
|
17
|
18
|
||||||||||||||||||||||||||||||
x
|
3
|
15
|
14
|
6
|
9
|
18
|
||||||||||||||||||||||||||||||
N=20
|
||||||||||||||||||||||||||||||||||||
a
|
2、4、5、6、8、10、12、14、15、16、18
|
3
|
7
|
9
|
||||||||||||||||||||||||||||||||
x
|
無解
|
7
|
3
|
9
|
||||||||||||||||||||||||||||||||
a
|
11
|
13
|
17
|
19
|
||||||||||||||||||||||||||||||||
x
|
11
|
17
|
13
|
19
|
||||||||||||||||||||||||||||||||
