Strong coprimality and
strong coprime primes

KEYWORDS: divisorial, coprimorial, strong coprimorial, strong coprime primes, strong coprimality triangle, divisors, common divisors, safe primes, supersafe primes, tau, phi, sigma.

Concerned with sequences: A181832, A181830, A181831, A181834, A181835, A181836, A181837, A181833, A181838, A059957, A007955, A001783, A001221, A005385, A000010, A000005.

The divisorial and the coprimorial

The coprimorial A001783 can be written as

\prod _{\stackrel {1\leq k\leq n}{k\perp n}}k

I prefer the name `coprimorial´ to `phitorial´. Similarly the divisorial A007955 is defined as

\prod _{\stackrel {1\leq k\leq n}{k\mid n}}k

Now, what is the ratio coprimorial / divisorial ? It turns out that we have to compare the coprimorial of n with the divisorial of n − 1 to get integer values. Then we can define

{\frac {\prod _{\stackrel {1\leq k\leq n}{k\perp n}}k}{\prod _{\stackrel {1\leq k<n}{k\mid (n-1)}}k}}

For n ≥ 0 this sequence starts
1, 1, 1, 1, 1, 3, 1, 20, 15, 35, 7, 36288, 35, 277200, 1485, 4576, 9009, 20432412000, 5005, 1097800704000, 459459, 5912192, 2834325, 2322315553259520000, 1616615

Surprisingly this sequence was not yet in the database.

Definitions

Let a and b be integers.

a divides b (`a | b´)
iff a is in the set of the divisors of b.
a is prime to b (`a ⊥ b´)
iff the set of common positive divisors of a and b is {1}.
a is strongly prime to b (`a $\scriptstyle {\underline {\perp }}$ b´)
iff a is prime to b and a does not divide b − 1.

We also suggest to write m $\scriptstyle {\underline {\perp }}$ n for `m strongly prime to n´ using the Unicode character U+234A (or with TeX \underline{\perp}) extending the proposal to write m ⊥ n for `m prime to n´.

Our terminology follows the plea of Knuth, Graham and Patashnik in Concrete Mathematics, p.115.

Hear us, O mathematicians of the world! Let us not wait any longer! We can make many formulas clearer by defining a new notation now! Let us agree to write m ⊥ n, and to say "m is prime to n", if m and n are relatively prime.

Recall that a strong reason for this notation comes from the fact that

{m\perp n}\iff m_{p}\;n_{p}=0\ {\text{for all }}p.

m_p is the exponent of the prime p in the prime factorization of m. Thus the dot product is zero, like orthogonal vectors (CM, (4.29)).

Using this terminology we can also write (p here always denotes a prime)

{m\ {\underline {\perp }}\ n}\iff {\begin{cases}m_{p}\;n_{p}=0&\forall \;p\;;\\m_{p}\;>(n-1)_{p}&\exists \;p\;.\end{cases}}

The concept of strong coprimality seems to be new. If I am wrong and you know a reference to an earlier mention please give me a notice.

A181830(n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}1

A181831(n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}k

A181832(n)=\prod _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}k

Let us fix some notation. Euler's φ(n) is the number of k prime to n and Φ(n), the number of k strongly prime to n, is the strong totient of n. The number of positive integers less than or equal to n that are not strongly prime to n is n - Φ(n), the strong cototient of n. For the number of divisors we will write τ(n).

\tau (n)=\sum _{\stackrel {1\leq k\leq n}{k\mid n}}1,\ \varphi (n)=\sum _{\stackrel {1\leq k\leq n}{k\perp n}}1,\ \Phi (n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}1

n	k prime to n {k ⊥ n}	k divides n − 1 {k>0 \| n − 1}	k strongly prime to n {k $\scriptstyle {\underline {\perp }}$ n}	Φ(n) A181830	Sum A181831	Prod A181832	n − Φ(n) A181833
0	{}	{1}	{}	0	0	1	0
1	{1}	{}	{1}	1	1	1	0
2	{1}	{1}	{}	0	0	1	2
3	{1,2}	{1,2}	{}	0	0	1	3
4	{1,3}	{1,3}	{}	0	0	1	4
5	{1,2,3,4}	{1,2,4}	{3}	1	3	3	4
6	{1,5}	{1,5}	{}	0	0	1	6
7	{1,2,3,4,5,6}	{1,2,3,6}	{4,5}	2	9	20	5
8	{1,3,5,7}	{1,7}	{3,5}	2	8	15	6
9	{1,2,4,5,7,8}	{1,2,4,8}	{5,7}	2	12	35	7
10	{1,3,7,9}	{1,3,9}	{7}	1	7	7	9
11	{1,2,3,4,5, 6,7,8,9,10}	{1,2,5,10}	{3,4,6, 7,8,9}	6	37	36288	5
12	{1,5,7,11}	{1,11}	{5, 7}	2	12	35	10
13	{1,2,3,4,5,6,7,8, 9,10,11,12}	{1,2,3, 4,6,12}	{5,7,8,9, 10,11}	6	50	277200	7
14	{1,3,5,9,11,13}	{1,13}	{3, 5, 9, 11}	4	28	1485	10
15	{1,2,4,7,8,11,13,14}	{1,2,7,14}	{4, 8, 11, 13}	4	36	4576	11
16	{1,3,5,7,9,11,13,15}	{1,3,5,15}	{7, 9, 11, 13}	4	40	9009	12

The strong coprimality triangle

Let divisors(n) denote the set of positive divisors of n and note that we set divisors(0) = {} (the empty set) and tau(0) = 0 by convention. This is not a mathematical definition but a convenient way to handle the case n = 0; for instance this is the way the symbolic mathematics program Maple implements this case. But also note that the sequences A027750 and A000005 start at offset 1.

With this definition, when we say "k is strongly prime to n" this corresponds to the following set equations, which subtract from the set of positive numbers prime to n the set of positive divisors of n − 1.

[n=0]  {}           minus {1}       = {},
[n=1]  {1}          minus {}        = {1},
[n=2]  {1}          minus {1}       = {},
[n=3]  {1, 2}       minus {1, 2}    = {},
[n=4]  {1, 3}       minus {1, 3}    = {},
[n=5]  {1, 2, 3, 4} minus {1, 2, 4} = {3}.

For example 1 is strongly prime to 1 and 3 is strongly prime to 5, and for every other pair (0 ≤ k ≤ n, 0 ≤ n ≤ 5) k is not strongly prime to n.

This immediately translates to the indicator function of strong coprimality, conveniently written as a triangle T(n,k) read by rows, 0 ≤ n and 0 ≤ k ≤ n.

[n=0]          0
[n=1]         0, 1
[n=2]       0, 0, 0
[n=3]      0, 0, 0, 0
[n=4]    0, 0, 0, 0, 0
[n=5]   0, 0, 0, 1, 0, 0

T(n, k) = [k is strongly prime to n] where [ ] denotes the Iverson bracket. The resulting sequence is A181837 =

0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,

Safe primes and primes not strongly prime to n

// safe primes
A005385_list := n->select(i->isprime(iquo(i,2)),
select(i->isprime(i),[$1..n])):

A005385_list(800);
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 
359, 383, 467, 479, 503, 563, 587, 719

Additionally set

A181833 := n -> n - A181830(n): 
SavePrimes := n -> `if`(A181833(n) = 5, n, NULL):

Now the observation is:

seq(SavePrimes(i),i=0..350);
A005385_list(350);

   7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347

In other words: The safe primes are precisely those integers n > 5 whose number of integers which are not strongly prime to n is 5. This fact can be easily visualized.

The safe prime triangle

The safe prime triangle is a subtriangle of the strong coprimality triangle generated by deleting the first 3 and the last 2 entries in each row. It is displayed below.

If in the safe prime triangle (starting with row number 0) a row n has exactly one `0´ entry, then n+5 is a safe prime. This way all safe primes greater 5 can be found by inspecting the triangle.

n is prime and (n − 1) / 2 is an odd prime

\iff n=\Phi (n)+5.

Proof ⇒. Since n is prime φ(n) = n − 1. Since (n − 1) / 2 is an odd prime

\tau (n-1)={\text{card}}\{1,2,(n-1)/2,n-1\}=4.

Thus

\Phi (n)=\varphi (n)-\tau (n-1)=n-5.

Proof ⇐. Exercise?

Super safe primes and super duper safe primes and ...

// safe primes
A005385_list := n->select(i -> isprime(iquo(i,2)),
select(i -> isprime(i),[$1..n])):

// supersafe primes 
A181841_list := n->select(i -> isprime(iquo(i,3)),
select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n]))):

A181841_list(5000);
7, 11, 23, 59, 179, 383, 503, 719, 1319, 1439, 1823, 
2579, 2903, 3119, 3779, 4283, 4679, 4703

Of course this process can be continued. So let us state it in a concise form.

SuperPrimes := proc(n, L) local sel, l;
sel := (k, M) -> select(i -> isprime(iquo(i,k)),M);
select(i -> isprime(i),[$1..n]);
for l in L do sel(l, %) od end:

With this little machine I can generate more new prime sequences than I could scribble in the margins of this page. So let us look only at a few basic instances.

SuperPrimes (110, [1])	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109
SuperPrimes (1000, [2])	5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983
SuperPrimes (600, [3])	7, 11, 17, 23, 41, 53, 59, 71, 89, 113, 131, 179, 239, 251, 269, 293, 311, 383, 419, 449, 491, 503, 521, 593, 599
SuperPrimes (6000, [2,3])	7, 11, 23, 59, 179, 383, 503, 719, 1319, 1439, 1823, 2579, 2903, 3119, 3779, 4283, 4679, 4703, 5099, 5639, 5939
SuperPrimes (80000,[2,3,5])	11, 59, 1319, 5099, 5939, 12659, 21059, 24659, 44819, 49019, 62639, 74759, 76919
SuperPrimes (40000,[2,3,7])	23, 503, 8819, 10079, 13523, 18743, 23099, 23603, 26459, 28643, 32603, 37463, 39983

Case [1] are the prime numbers, [2] the safe primes, [3] is A162337, [2, 3] are the super-safe primes. The nice thing is that you can call this function with any list of positive integers [a,b,c,...,o]. Have fun exploring!

Strong coprime primes

The notions considered above can be constrained (or reduced) to the domain of nonnegative primes (yes, -2 is also a prime, though not a very popular one). This is what we will do now. There is no standard terminology for the classical case of coprimality on which we can build here. However, note that 3 out of the 4 sequences describing the classical case of coprime primes are already in the database (see the link table in the summary below).

n	strongly prime to n {k $\scriptstyle {\underline {\perp }}$ n}	primes strongly prime to n	Card A181834	Sum A181835	Prod A181836	π(n) − Card AX
0	{}	{}	0	0	1	0
1	{1}	{}	0	0	1	0
2	{}	{}	0	0	1	1
3	{}	{}	0	0	1	2
4	{}	{}	0	0	1	2
5	{3}	{3}	1	3	3	2
6	{}	{}	0	0	1	3
7	{4, 5}	{5}	1	5	5	3
8	{3, 5}	{3, 5}	2	8	15	2
9	{5, 7}	{5, 7}	2	12	35	2
10	{7}	{7}	1	7	7	3
11	{3, 4, 6, 7, 8, 9}	{3, 7 }	2	10	21	3
12	{5, 7}	{5, 7}	2	12	35	3
13	{5, 7, 8, 9, 10, 11}	{5, 7, 11}	3	23	385	3
14	{3, 5, 9, 11}	{3, 5, 11}	3	19	165	3
15	{4, 8, 11, 13}	{11, 13}	2	24	143	4
16	{7, 9, 11, 13}	{7, 11, 13}	3	31	1001	3

Note that AX(n) = A059957(n-1) for n ≥ 2. Although AX(n) has a more natural and fundamental definition, AX(n) = π(n) - A181834(n), and, more important, future work would profit if all 8 sequences in the two tables above are enumerated uniformly, I will not submit it to stay in accordance with OEIS submission policy and only add some remarks to A059957.

From the comments in A059957 we see that if AX(n) = 2, then n and n − 1 are prime powers (in the sense which does not force 1 to be a prime power).

seq(`if`(AX(n) = 2, n, NULL),n=0..300);
3, 4, 5, 8, 9, 17, 32, 128, 257,

The related sequences A006549 and A120430 assume or imply that 1 is a prime power. But since we are talking about pairs of integers the most natural sequence in this context is possibly:

`union`(seq(`if`(AX(n)=2,{n-1,n},NULL),n=0..300));
2, 3, 4, 5, 7, 8, 9, 16, 17, 31, 32, 127, 128, 256, 257,

With this definition no `1´ annoys here the lordly Fermat and Mersenne primes anymore. However, this sequence is not (yet) in the database. Finally we translate the formulas given by Labos E. in A059957 to our setup. For n ≥ 2

AX(n) = A001221(n^2-n) 
      = A001221(n-1)+A001221(n) 
      = A001221(A002378(n-1)).

Robert P. Munafo's notable sequence

Citing from the A069354 definition: Lowest base with simple divisibility test for n primes; smallest B such that ω(B) + ω(B − 1) = n. Example: a(4) = 15 because in base 15 you can test for divisibility by 4 different primes (3 and 5 directly, 2 and 7 by "casting out 14's").

A069354_list := proc(n) local i, L, Max;
Max := 1; L := NULL;
for i from 2 to n do 
   if nops(numtheory[factorset](i*(i-1))) = Max
   then Max := Max + 1; L := L,i fi;
od;
L end:

A069354_list(720);
2, 3, 6, 15, 66, 210, 715, 

# And now compare with:

B069354_list := proc(n) local i, L, Max;
Max := 0; L := NULL;
for i from 0 to n do 
   if AX(i) > Max # for AX see Maple code below
   then Max := AX(i); L := L,i fi;
od;
L end:

# Both sequences are identical, though the 
# second computation is much slower.

Thus in our setup Munafo's A069354 lists those indices of AX (the number of primes ≤ n that are not strongly prime to n) which increase for the first time the value relative to all predecessors (new maximum).

Now, what happens if we use (the corresponding) A051953 (number of primes ≤ n that are not prime to n) instead of AX in the above search? Lo and behold! We get the primorial numbers A002110! In turn this leads us to look at the prime factors of Munafo's sequence:

2, 3, 2*3, 3*5, 2*3*11, 2*3*5*7, 5*11*13, 5*7*11*19, 
3*13*23*43,3*7*17*23*31, 5*11*17*19*41, 5*7*11*19*29*53,
2*7*11*13*23*31*41

Can you spot a pattern?

Min and max values of the set of strong coprimes

seq(min(op(StrongCoprimes(i))),i=0..20);
∞, 1, ∞, ∞, ∞, 3, ∞, 4, 3, 5, 7, 3, 5, 5, 3, 4, 7, 3, 5, 4, 3
seq(max(op(StrongCoprimes(i))),i=0..18);
-∞, 1, -∞, -∞, -∞, 3, -∞, 5, 5, 7, 7, 9, 7, 11, 11, 13, 13, 15

We will set the minimum and and the maximum of the empty set to 0, by convention. The corresponding sequences are A181839 and 181840.

Summary

	card	sum	prod	#n - card
k prime to n	A000010	A023896	A001783	A051953
p prime to n	A048865	A066911	A066838	A001221
k strongly prime to n	A181830	A181831	A181832	A181833
p strongly prime to n	A181834	A181835	A181836	A059957

indicator [k $\scriptstyle {\underline {\perp }}$ n]	A181837	indicator prime [p $\scriptstyle {\underline {\perp }}$ n]	A181838
min_k{k $\scriptstyle {\underline {\perp }}$ n}	A181839	max_k{k $\scriptstyle {\underline {\perp }}$ n}	A181840
safe primes	A005385	super safe primes	A181841

Maple code

with(numtheory):

Primes      := n -> select(k->isprime(k),{$1..n}):
divisorial  := proc(n) local i; mul(i,i=divisors(n)) end:
coprimorial := proc(n) local i;
             mul(i,i=select(k->igcd(k,n)=1,[$1..n])) end:
             
Triangle := proc(N, C)
local T, L, k, n;
  for n from 0 to N do
      T := C(n);
      L := NULL;
      for k from 0 to n do 
        L := L, `if`(member(k,T),1,0)
      od;
      print(L)
   od
end:

############ coprimality ###################

Coprimes := n -> select(k->igcd(k,n)=1,{$1..n}):
A000010 := n -> nops(Coprimes(n)): 
A023896 := proc(n) local i; add(i,i=Coprimes(n)) end:
A001783 := proc(n) local i; mul(i,i=Coprimes(n)) end:
 
# These functions can also be be computed as
A000010a := n -> `if`(n=0,0,phi(n)):
A023896a := n -> `if`(n<2,n,n*phi(n)/2):
A001783a := n -> `if`(n=0,1,coprimorial(n)):
 
CoprimePrimes := n -> Primes(n) intersect Coprimes(n):
A048865 := n -> nops(CoprimePrimes(n)): 
A066911 := proc(n) local i; add(i,i=CoprimePrimes(n)) end:
A066838 := proc(n) local i; mul(i,i=CoprimePrimes(n)) end:
 
# These functions can also be be computed as
CP := n -> Primes(n) minus factorset(n):
A048865a := n -> nops(CP(n)):
A066911a := proc(n) local i; add(i,i=CP(n)) end:
A066838a := proc(n) local i; mul(i,i=CP(n)) end:

CoprimalityTriangle := n -> Triangle(n,Coprimes):
CoprimesTriangle    := n -> Triangle(n,CoprimePrimes):

############ strong coprimality ###################

StrongCoprimes := n -> 
select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
A181830 := n -> nops(StrongCoprimes(n)): 
A181831 := proc(n) local i; add(i,i=StrongCoprimes(n)) end:
A181832 := proc(n) local i; mul(i,i=StrongCoprimes(n)) end:

# These functions can also be be computed as
A181830a := n -> `if`(n=0,0,phi(n)-tau(n-1)):
A181831a := n -> `if`(n<2,n,n*phi(n)/2-sigma(n-1)):
A181832a := n -> `if`(n=0,1,coprimorial(n)/divisorial(n-1)):

StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A181834 := n -> nops(StrongCoprimePrimes(n)): 
A181835 := proc(n) local i; add(i,i=StrongCoprimePrimes(n)) end:
A181836 := proc(n) local i; mul(i,i=StrongCoprimePrimes(n)) end:
AX      := n -> nops(Primes(n)) - nops(StrongCoprimePrimes(n)):

# These functions can also be be computed as
SCP := n -> Primes(n) minus factorset((n-1)*n):
A181834a := n -> nops(SCP(n)):
A181835a := proc(n) local i; add(i,i=SCP(n)) end:
A181836a := proc(n) local i; mul(i,i=SCP(n)) end:
AXa      := n -> `if`(n<2,0,nops(factorset((n-1)*n))):

StrongCoprimalityTriangle  := n -> Triangle(n,StrongCoprimes):
StrongCoprimePrimesTriangle:= n -> Triangle(n,StrongCoprimePrimes):

Acknowledgment

While writing this page I was inspired by several sequences in the database. The authors of the (non classical) sequences which were most valuable to me are: Lábos Elemér (A048865, A051953, A059957), Leroy Quet (A066911, A066838, A131187), R. P. Munafo (A069354) and Olivier Gérard (A023896).

User:Peter Luschny/StrongCoprimality

Contents

Strong coprimality and
strong coprime primes

The divisorial and the coprimorial

Definitions

The strong coprimality triangle

Safe primes and primes not strongly prime to n

The safe prime triangle

Super safe primes and super duper safe primes and ...

Strong coprime primes

Robert P. Munafo's notable sequence

Min and max values of the set of strong coprimes

Summary

Maple code

Acknowledgment

See also

Navigation menu

Views

Personal tools

Navigation

Search

Tools

User:Peter Luschny/StrongCoprimality

Contents

Strong coprimality and strong coprime primes

The divisorial and the coprimorial

Definitions

The strong coprimality triangle

Safe primes and primes not strongly prime to n

The safe prime triangle

Super safe primes and super duper safe primes and ...

Strong coprime primes

Robert P. Munafo's notable sequence

Min and max values of the set of strong coprimes

Summary

Maple code

Acknowledgment

See also

Navigation menu

Search

Strong coprimality and
strong coprime primes