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,5

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.

Links

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

Example

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.

Crossrefs

Cf. A005385, A000010.

Sequence in context: A134033 A185051 A095026 * A094367 A092368 A225080

Adjacent sequences: A184994 A184995 A184996 * A184998 A184999 A185000

Keyword

nonn,mult

Author

Krzysztof Ostrowski, Apr 24 2011

Status

approved