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

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, 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, 17, 27, 57, 3, 59, 29, 15, 16, 33, 9, 65, 15, 21, 15, 69, 6, 71, 35, 15, 17, 45, 11, 77, 12

Offset: 1

Author

Krzysztof Ostrowski, Apr 24 2011

Keywords

• nonn
• mult

Comments

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:

1) r is coprime to n,

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).

If one of these conditions isn't satisfied then either p or (p-1)/2 isn't a prime number.

If n1 and n2 are coprime then a(n1*n2) = a(n1)*a(n2), per the Chinese remainder theorem.

Examples

			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.
		

Links

• Krzysztof Ostrowski, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A005385, A000010.