|
%I #33 Mar 31 2012 10:27:23
%S 1,1,1,1,3,1,5,2,3,3,9,1,11,5,3,4,15,3,17,3,5,9,21,2,15,11,9,5,27,3,
%T 29,8,9,15,15,3,35,17,11,6,39,5,41,9,9,21,45,4,35,15,15,11,51,9,27,10,
%U 17,27,57,3,59,29,15,16,33,9,65,15,21,15,69,6,71,35,15,17,45,11,77,12
%N Number of distinct remainders that are possible when a safe prime p is divided by n (for p > 2*n+1).
%C A number r could be a remainder of division p/n (for n > 0 and safe prime p > 2*n+1) if it satisfies two conditions:
%C 1) r is coprime to n,
%C 2) (r-1)/2 is coprime to n (assuming r-1 is even) or (n+r-1)/2 is coprime to n (assuming n+r-1 is even).
%C If one of these conditions isn't satisfied then either p or (p-1)/2 isn't a prime number.
%C If n1 and n2 are coprime then a(n1*n2) = a(n1)*a(n2), per the Chinese remainder theorem.
%H Krzysztof Ostrowski, <a href="/A184997/b184997.txt">Table of n, a(n) for n = 1..10000</a>
%e a(60) = 3 as there are only three distinct remainders possible (23, 47 and 59) when dividing some safe prime p by 60. It's true for all safe primes except 5, 7 and 11.
%Y Cf. A005385, A000010.
%K nonn,mult
%O 1,5
%A _Krzysztof Ostrowski_, Apr 24 2011
|
