cp's OEIS Frontend

A184997 Number of distinct remainders that are possible when a safe prime p is divided by n (for p > 2*n+1).

%I A184997 #33 Mar 31 2012 10:27:23
%S A184997 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 A184997 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 A184997 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 A184997 Number of distinct remainders that are possible when a safe prime p is divided by n (for p > 2*n+1).
%C A184997 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 A184997 1) r is coprime to n,
%C A184997 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 A184997 If one of these conditions isn't satisfied then either p or (p-1)/2 isn't a prime number.
%C A184997 If n1 and n2 are coprime then a(n1*n2) = a(n1)*a(n2), per the Chinese remainder theorem.
%H A184997 Krzysztof Ostrowski, <a href="/A184997/b184997.txt">Table of n, a(n) for n = 1..10000</a>
%e A184997 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 A184997 Cf. A005385, A000010.
%K A184997 nonn,mult
%O A184997 1,5
%A A184997 _Krzysztof Ostrowski_, Apr 24 2011