A323550 Numbers that can be expressed as (p - 1)*(q - 1) + 1, where p < q are primes.

3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 29, 31, 33, 37, 41, 43, 45, 47, 49, 53, 57, 59, 61, 65, 67, 71, 73, 79, 81, 83, 85, 89, 93, 97, 101, 103, 105, 107, 109, 113, 117, 121, 127, 131, 133, 137, 139, 141, 145, 149, 151, 157, 161, 163, 165, 167, 169, 173, 177, 179, 181, 185, 191, 193, 197, 199, 201, 205, 209

Offset: 1

Author

Andres Cicuttin, Jan 17 2019

Keywords

• nonn

Comments

If p < q are primes and a(n) = (p - 1)*(q - 1) + 1, then x^a(n) == x (mod p*q) for every integer x.

Examples

			181 is a term because 181 = (11 - 1)*(19 - 1) + 1. - _Bernard Schott_, Jan 19 2019
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• A. Bogomolny, Euler Function and Theorem

Crossrefs

Cf. A065091.

Programs

Maple

N:= 1000: # for terms <= N
S:= {}:
P:= select(isprime,[2,seq(i,i=3..N,2)]): nP:= nops(P):
for i from 1 to nP do
  for j from i+1 to nP do
     v:= (P[i]-1)*(P[j]-1)+1;
     if v > N then break fi;
     S:= S union {v}
od od:
sort(convert(S,list)); # Robert Israel, May 22 2025

Mathematica

nmax = 100;
pairs = Table[Table[(Prime[i] - 1)*(Prime[j] - 1) + 1, {i, 1, j - 1}], {j, 2,Prime[nmax]}];
(DeleteDuplicates@Sort@Flatten@pairs)[[1 ;; nmax]]

PARI

isok(n) = {if (n % 2, forprime(p = 2, n, forprime(q = p+1, n, if (n == (p - 1)*(q - 1) + 1, return (1)););););} \\ Michel Marcus, Feb 25 2019