６．合同数の判定条件

ある数が合同数か否かを判定する方法が、いくつか『数論における未解決問題集』で紹介されている。

以下の場合は合同数となる。

• mod 8 で 5 と合同な素数（C5）
• mod 8 で 7 と合同な素数（C7）
• mod 8 で 6 と合同で、かつ、その半分が素数となるような数（C6）

以下の場合は合同数とならない。

• mod 8 で 3 と合同な素数（N3）
• そのような２数の積（N9）
• mod 8 で 5 と合同な素数の２倍（NX）
• mod 8 で 5 と合同な素数の２つの積の２倍（NL）
• mod 16 で 9 と合同な素数の２倍（N2）

J. B. Tunnell は、任意の数に対する判定条件を与えた。

出典

J. B. Tunnell, "A Classical Diophantine Problem and Modular Forms of Weight 3/2", Inventiones mathematicae, 72(1983)323-334
志賀弘典、『楕円曲線の水系』、数理科学、No.390, Dec. 1995

奇数自然数ｎが合同数であるためには、次の条件が満たされることが必要十分：
　「x²＋2y²＋8z²＝ｎ の整数解の個数」
＝「x²＋2y²＋32z²＝ｎ の整数解の個数」×２

偶数については、
　「x²＋4y²＋8z²＝n/2 の整数解の個数」
＝「x²＋4y²＋32z²＝n/2 の整数解の個数」×２

（注：『整数解』なので、負の場合も解となる。）

プログラム

 10   ' set cong : s_cong.ub
 20   word 4:N%=10000:dim T(N%),S(N%):T(1)="□":S(1)=T(1):D%=0
 30   for I%=2 to N%
 40     if moeb(I%)=0 then T(I%)="□" else T(I%)=""
 50     S(I%)=T(I%)
 60   next I%
 70   ' N3, C5, C7
 80   for I%=2 to N%
 90     if and{prmdiv(I%)=I%,I%@8=3} then T(I%)="N3"
100     if and{prmdiv(I%)=I%,I%@8=5} then T(I%)="C5"
110     if and{prmdiv(I%)=I%,I%@8=7} then T(I%)="C7"
120   next I%
130   ' C6
140   for I%=6 to N% step 8:J%=I%\2:if prmdiv(J%)<J% then 160
150     if T(I%)="" then T(I%)="C6"
160   next I%
170   ' NX
180   for I%=5 to N%\2 step 8:if prmdiv(I%)<I% then 200
190     if T(I%*2)="" then T(I%*2)="NX"
200   next I%
210   ' N9
220   for I%=3 to N% step 8:if prmdiv(I%)<I% then 270
230     for J%=I% to N% step 8:if prmdiv(J%)<J% then 260
240       if I%*J%>N% then cancel for:goto 270
250       if T(I%*J%)="" then T(I%*J%)="N9"
260     next J%
270   next I%
280   ' NL
290   for I%=5 to N% step 8:if prmdiv(I%)<I% then 340
300     for J%=I% to N% step 8:if prmdiv(J%)<J% then 330
310       if 2*I%*J%>N% then cancel for:goto 340
320       if T(2*I%*J%)="" then T(2*I%*J%)="NL"
330     next J%
340   next I%
350   ' N2
360   for I%=9 to N%\2 step 16:if prmdiv(I%)<I% then 390
370     if 2*I%>N% then cancel for:goto 410
380     if T(I%*2)="" then T(I%*2)="N2"
390   next I%
400   ' general criteria
410   for I%=2 to N%:if moeb(I%)=0 then 510
420     if T(I%)="" then T(I%)="  "
430     if even(I%) then 490
440     ' odd case
450     A%=fnSub(I%,2,8):B%=fnSub(I%,2,32)
460     if A%=(B%*2) then S(I%)="C" else S(I%)="N"
470     goto 510
480     ' even case
490     A%=fnSub(I%\2,4,8):B%=fnSub(I%\2,4,32)
500     if A%=(B%*2) then S(I%)="C" else S(I%)="N"
510   next I%
520   '
530   for I%=2 to N%-2:print I%;": ";T(I%);":";S(I%)
540   next I%:print "count=";D%
550   end
560   '
570   fnSub(N%,P%,Q%)
580   local X%,Y%,Z%,A%,B%,C%,D%
590   D%=0:C%=isqrt(N%/Q%)
600   for Z%=C% to -C% step -1
610     B%=isqrt((N%-Q%*Z%^2)/P%)
620     for Y%=B% to -B% step -1
630       A%=N%-Q%*Z%^2-P%*Y%^2:if A%<0 then 660
640       X%=isqrt(A%):if res>0 then 660
650       inc D%:if X%>0 then inc D%:' print N%;":";X;Y%;Z%
660     next Y%
670   next Z%
680   return(D%)

このプログラムを実行させると、1000以下の合同数は確かに361個となる。
また 10000以下の合同数は 3503個 であることがわかる。