Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|Fortran}}: Ah, division.
(→{{header|Fortran}}: Ah, division.) |
|||
Line 386:
MOD(3 + MOD(D,3),3) 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
</pre>
Thus, <code>MOD(-1,1) + MOD(3,3) = -1 + 0</code> but <code>MOD(3,3) = 0</code> so that ''(a + b) mod n'' does not come out as ''[(a mod n) + (b mod n)] mod n'' as might be expected. However, this is consistent with integer division that truncates. If ''q·f = n/d'' where q is the integer part and f the fractional part of the division, then the remainder is ''fd'' and has a sign too.
Integer arithmetic can be a delicate matter, not just because of overflows. With division, sometimes the formula will never produce a remainder, as in n(n + 1)/2, and sometimes the divisor is always a factor for more complex reasons. But if a term produces a fractional part, is it to be discarded or not? Some languages (such as Pascal) insist on "div" instead of "/" so that one thinks about truncating division, others (such as pl/i) just generate the fractional part and proceed: perhaps the result will round? truncate? to the desired value, or perhaps other terms will cancel out the fractional parts and all will be well, or, perhaps they will combine and the result will be out by one, ''etc''. And some formulae require the fractional parts, as in the expression for the n'th Fibonacci number:
<math>\frac{1}{\sqrt{5}}\left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right]</math>
where each term generates an ''infinite'' non-repeating fractional part, and, they cancel ''exactly'', even for large values of n...
Here I am supposing that ''(h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3'' is evaluated as ''{[(h3 + Prime1)*(Prime1 - 1) mod d] == 0} and {[-(Prime1 squared) mod h3] == d mod h3}'' which is to say it is ''[-(Prime1 squared)] mod h3'' not ''-[(Prime1 squared) mod h3]'' where the first case involves the MOD(negative number) while the second is -MOD(positive number) and the only way that result could match ''d mod h3'' is when both are zero.
| |||