Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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