|
|
> No.1811[元記事へ]
GAIさんへのお返事です。
> x^2≡a (mod b) を満たすxが存在するとき、aRb
> また、解が存在しないとき、aNb
> の記号を使用するものとし
：
> 平方剰余の相互法則によると、
> どちらかがピーチ味の素数なら、ＲかＮかが一致して
> また
> 両方がオレンジ味の素数なら、入れ替えた式は不一致が起こる。
>
> ということを確認したい。
>
> このことを色で判断できるプログラムを作っていただきたいのです。
色は付いていません。
!平方剰余の相互法則
LET N=25 !100以下の素数の個数
DIM M(N)
CALL PrimeList(N,M) !n個の素数列を返す
FOR i=2 TO N !奇素数の組合せ ※1番目の2を除く
LET a=M(i)
FOR j=2 TO i-1
LET b=M(j)
LET p=MOD(a,4) !素数の型 4k+1,4k+3
LET q=MOD(b,4)
PRINT p;q;
LET AB$=test$(a,b) !x^2≡a (mod b)が解を持つかどうか
PRINT " "; STR$(a); AB$; STR$(b);
LET BA$=test$(b,a)
PRINT " "; STR$(b); BA$; STR$(a)
IF (p=1 OR q=1) AND AB$=BA$ THEN !(R,R)、(N,N)
ELSE
IF (p=3 AND q=3) AND AB$<>BA$ THEN !(N,R)、(R,N)
ELSE
PRINT "議論と食違う"
STOP
END IF
END IF
NEXT j
NEXT i
END
EXTERNAL FUNCTION test$(a,b) !x^2≡a (mod b)を満たす非負整数xがあるかどうか確認する
LET t=MOD(a,b) !平方剰余
FOR x=0 TO b-1
IF MOD(x*x,b)=t THEN EXIT FOR
NEXT x
LET test$="R"
IF x>b-1 THEN LET test$="N" !存在しないなら
END FUNCTION
!試行割算法
EXTERNAL FUNCTION PrimeQ(n) !素数判定 1:素数、0:素数でない
LET PrimeQ=0
IF n<2 OR n<>INT(n) THEN EXIT FUNCTION !引数を確認する
!２以上の自然数なら
IF MOD(n,2)=0 THEN !２の倍数
IF n=2 THEN LET PrimeQ=1 !２は素数
ELSEIF MOD(n,3)=0 THEN !３の倍数
IF n=3 THEN LET PrimeQ=1 !３は素数
ELSE
LET k=5
DO WHILE k*k<=n !√nまで検証する
IF MOD(n,k)=0 THEN !5,11,17,23,29,…
EXIT FUNCTION
ELSEIF MOD(n,k+2)=0 THEN !7,13,19,25,31,…
EXIT FUNCTION
END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
LET k=k+6
LOOP
LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION
EXTERNAL SUB PrimeList(n,p()) !ｎ個の素数列を返す
IF n<1 THEN EXIT SUB !引数を確認する
LET c=1 !見つけた個数
LET p(c)=2 !２は素数
IF n=1 THEN EXIT SUB
LET c=2
LET p(c)=3
IF n=2 THEN EXIT SUB
LET k=5
DO
IF PrimeQ(k)<>0 THEN !5,11,17,23,29,… が素数なら
LET c=c+1
LET p(c)=k
IF c=n THEN EXIT DO
END IF
IF PrimeQ(k+2)<>0 THEN !7,13,19,25,31,…
LET c=c+1
LET p(c)=k+2
IF c=n THEN EXIT DO
END IF
!+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
LET k=k+6 !次へ
LOOP
END SUB
|
|