Abstract: This paper shows how to determine all those positive integers xsuch that ϕ(x) = mholds,

where xis of the form 2apbqcand p, q are distinct odd primes and a, b, c ∈N.

In this paper, we have shown how to determine all those positive integers nsuch that ϕ(x) = nwill

hold where nis of the form 2apbqc, where p, q are distinct odd primes and a, b, c ∈N. Such nare

called pre-totient values of 2apbqc. Several important theorems along with subsequent results have been

demonstrated through illustrative examples.

We propose a lower bound for computing quantity of the inverses of Euler’s function. We answer the

question about the multiplicity of min the equation ϕ(x) = m[1]. An analytic expression for exact

multiplicity of m= 22n+a, where a∈N,a < 2n,ϕ(x)=22n+awas obtained. A lower bound of

inverses number for arbitrary mwas found. We make an new approach to Sierpinski assertion.

Key-Words: Inverses of Euler’s totient function, prime numbers, number of pre-totients of Euler’s totient

function, lower bound of the inverses of Euler’s function.

1 Introduction

The Euler totient function ϕ(n)for n∈Nis the total

number of positive integers which are less than nand

coprime with n.

Let nbe a positive integer. Then the set Z∗

ncon-

taining the positive integers less than or equal to n

and relatively prime to nforms a group under multi-

plication modulo nand the order of this group is de-

noted by ϕ(n), known as Euler’s phi function or the

totient function. For example, Z∗

8={1,3,5,7}and

So ϕ(8) = 4. Similarly, ϕ(11) = 10 because Z∗

11 =

{1,2, . . . , 10}.

In number theory and abstract algebra, Euler’s phi

function plays a major role in several aspects. There

are several important properties and rules to deter-

mine the value of ϕ(n)for given n∈Nwhich can

be found in many standard text books related to num-

ber theory.

(1) If a, b are relatively prime integers, then

ϕ(ab) = ϕ(a)ϕ(b). An immediate consequence of

this property is, ϕ(2em) = ϕ(2e)ϕ(m)provided

m∈Nis odd and e∈N.

This is an application of our theorem on the num-

ber of solutions to an equation with the Euler function

i.e. search for the preimage of the Euler function in

cryptography. Since pand qare prime numbers, then

ϕ(pq) = ϕ(n) = (p−1)(q−1), where ϕ(x)is the Eu-

ler function. From the condition of choosing the key d

as mutually inverse to ewe have: de(modϕ(n)) ≡1,

or de =kϕ(n)+1for some natural k. Then using

Euclid algorithm one can find secret key d. Solving

the last equation with respect to d, we actually find the

secret key in algorithm RSA [24]. Therefore, in order

for this equation to be solved, it is extremely neces-

sary that the possible solutions, i.e. the pre-totients of

the function ϕ(n), be as large as possible. Therefore,

it is important for us to learn to choose such n=pq

that the set ϕ−1(n)is as large as possible for num-

bers nof this order. To find ϕ(n)we can consider

the Sylow p1-subgroup and Sylow q1-subgroup of Z∗

and compute their orders, where pq is divisible on

p1and Q1. Orders of p1-subgroup and q1-subgroup

[16, 18, 17, 19] of Z∗

ndepends from its structure and

multiplicity p1and q1in p−1and q−1because of

ord(Z∗

n) = (p−1)(q−1).

2 Preliminaries and Notifications

In order to make the presentation simpler, we shall

make use of the following symbols. For a, b, n ∈N,

Nn={1,2, ..., n −1, n},

aNb={a, a + 1, a + 2, ..., b −1, b},

aNn={x∈N:x≥a},

Wn={1,2, ..., n −1, n},

W={0} ∪ N,

RUSLAN SKURATOVSKII

Interregional Academy of Personnel Management Kiev, and

National Aviation University, Kiev

and Igor Sikorsky Kiev Polytechnic Institute

The Investigation of Euler’s Totient Function Preimages

Pre-totients in General Case

and the Cardinality of

for ϕ(n)= 2mpα

1pβ

Received: April 7, 2021. Revised: December 22, 2021. Accepted: January 17, 2022. Published: February 9, 2022.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

Kyiv, UKRAINE

P={p∈N|pis a prime number }.

We shall use the symbol |S|to denote the number

of elements of the set S. When a positive integer |x|is

given, one can compute ϕ(x)easily. But when ϕ(x)

is given, determination of xbecomes comparatively

a difficult task. Here the values ϕ(x)is called a to-

tient number whereas its preimage xunder ϕis called

a pre-totient. Corresponding to a given n∈N, the

collection of all pre-totients of nunder ϕis denoted

by ϕ−1(n)i.e. ϕ−1(n) = {r∈N:ϕ(r) = n}.

For example, ϕ−1(2) = {3,4,6}. The number

14 has no pre-totients and so ϕ−1(14) is empty set.

Moreover, if n > 2is odd, then ϕ−1(n)is an empty

set because of the set property 4 given above.

In [2], a general process to determinate the set ϕ−1(n)

is discussed along with an example for n= 576.

However the process demands the assumption that

all ϕ−1(x)where x < 576 must be known before-

hand. Once this table is prepared, the actual determi-

nation starts. Another set of works can be found in [2]

and [11]. In [11] the determination is done through

algorithm, which way become tedious job when n

will become severely bigger. In [2] works of deter-

mination of pre-totients of some particular cases like

n= 2p, 2kpwhere pis odd prime have been made.

Carmichael showed his process for determination of

pre-totients of the number of the form 2min [4]. We

also did his work on the same set ϕ−1(22n+a)in our

work in arxiv [12].

In this paper we are considering those nthat have

the form n= 2apa1

1pa2

2, where a,a1,a2∈Nand

p1< p2are distinct odd primes in an alternative man-

ner. To proceed further, we assume that x∈φ−1(n).

Then xis either even or odd positive integer. For

n∈N, we take into account the following partition

into two sets introduced in [2].

E(n) = x∈ϕ−1(n) : x≡0(mod2)(1)

O(n) = x∈ϕ−1(n) : x≡1(mod2)(2)

Clearly, ϕ−1(n)is disjoint union of E(n)and

O(n). Moreover, the set of O(n)is empty provided

nis odd. In this case, ϕ−1(n) = E(n). In [2] it is

derived that cardinalities of the set O(2s)and E(2s),

where s is odd positive integer are equal. We now

start with the first case x∈E(2apa1

1pa2

2).

3 Problem Formulation

The aim of this work is to study theoretical numeri-

cal properties of the multivalued inversed to Euler’s

function [13, 14], demonstrate the relevance of the ex-

amples.

Subject of study: explore the composition of the

function ϕ(n)with itself and the tasks associated with

it, it’s properties, the number of preimages of the

function ϕ(n), behavior of the straight O(An), where

An(n;ϕ(n)) and O(0; 0) where n→ ∞ [23].

Using Lenstra’s factorization method we have deal

with group of curve point isomorphic to multiplica-

tive group of ring Znwhich has order ϕ(n). Hence, it

is important to know size set of pre-totients for ϕ(n)

to choose suitable curve [22, 23].

We going to find a lower estimation for computing

quantity of the inverses of Euler’s function. Our ap-

proach can be further adapted for computing certain

functions of the inverses, such as their quantity, the

larger.

Of fundamental importance in the theory of num-

bers is Euler’s totient function ϕ(n). Two famous

unsolved problems concern the possible values of the

function A(m), the number of solutions of ϕ(x) = m,

also called the multiplicity of m. Of big importance

in the cryptography has number of pre-totients of Eu-

ler’s totient function ϕ(n), n =pq. Because it deter-

mines cardinal of secret key space in RSA [24].

4 Main result about solution of

ϕ(n) = 2mpα

1pβ

Firstly, we consider the case x∈E(2apa1

1pa2

2).

Theorem 4.1. Let x∈E(2apa1

1pa2

2). Then xcan

never be divisible by 2Pfor all p∈a+1N.

Proof. Let’s make the opposite assumption. Since

x∈E(2apa1

1pa2

2), we write x= 2a+rm0where m0=

2k−1and k, r ∈N. Then ϕ(x)=2apa1

1pa2

2lead us

to the contradiction:

2a+r−1ϕ(m0) = 2apa1

1pa2

2,(3)

2r−1ϕ(m0) = pa1

1pa2

2.(4)

In (4), if r−1∈N, then left hand side is even

number but right hand side is not, a contradiction. If

r−1 = 0 i.e. r= 1 then (4) reduces to ϕ(m0) =

pa1

1pa2

2. Since m0is odd, m0= 1 or m0≥3will

create contradiction in either way. This completes the

proof.

Theorem 4.2. For e∈Nathe set E(2apa1

1pa2

contains elements of the form 2em0, where

m0≡1(mod2) iff m0∈O(2a+1−epa1

1pa2

2).

Proof. Let x= 2em0, where e∈Naand m0is

odd. Then x∈E(2apa1

1pa2

2)gives us the following

chain of transformations: 2e−1ϕ(m0) = 2apa1

1pa2

which implies that ϕ(m0) = 2(a+1)−epa1

1pa2

2. Con-

sequently we obtain m0∈O(2(a+1)−epa1

1pa2

2).

On the other hand, if

O(2(a+1)−epa1

1pa2

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

be non-empty for e∈Na( we won’t take e=a+ 1

since O(pa1

1pa2

2)is empty set), then x= 2em0∈

E(2apa1

1pa2

2). Hence the proof is completed.

Corollary 2.3. Let qβbe a divisor of x∈

ϕ−1(2apα1

1pα2

2),q∈P\{2, p1, p2}. Then β= 1.

Proof. The proof follows from the opposite as-

sumption that n= 2eqβm∈ϕ−1(2apα1

1pα2

2), where

e∈Wa,m≡1(mod2)and GCD (q, 2m)=1.

Then, the initial number n= 2apa1

1pa2

can be presented in form of the product

2apa1

1pa2

2= 2e−1qβ−1(q−1) ϕ(m).If β−1∈N

then desired contradiction is already reached.

Statement. If m∈O(2apa1

1pa2

2)then mcontains

no greater than anumber of odd prime divisors.

Proof. Let m∈O(2apa1

1pa2

2). Then mis odd

and evidently m≥3. Hence any prime divisor of m

will be odd. Let the total number of such odd prime

divisors of mbe r. In other words, r∈Na.

Let the total number of such odd prime divisors of

mbe r. Then 2r|ϕ(m)or equivalently 2r|2apa1

1pa2

In other words, r∈Naor putting it simply number of

odd prime divisors of mis at most a.

Remark 4.1. Till October 2019 only

Fermat’s prime that have been discovered are

F0, F1, F2, F3, F4.From F5till F32 all composite.

Primality of F33, F34, F35 is still an open problem.

From F36, some of the Fermat’s numbers have been

established as composite. See [5, 8, 9], for latest up-

dates.

2.2 Let m=pβ1

1q2, then ϕ(m) = 2apa1

1pa2

2will

produce

2apa1+1−β1

1pa2

2= (p1−1)(q2−1).(5)

Let e1, e2are natural numbers. Evidently, β1∈

Na1+1 and q2=2apa1+1−β1

1pa2

p1−1+ 1∈P. More-

over, if we assume

p1−1 = 2e1,

q2−1 = 2e1pγ21

1pγ22

where

e1, e2∈N

and

γ21, γ22 ∈W

then

a=e1+e2,

a1=γ21 +β1−1,

a2=γ22.

Once again, p1is a Fermat’s prime Fe0

1for some

2e0

1∈Na−1and so e2=a−2e0

1. Consequently

we can state.

Theorem 4.3. m=pβ1

1q2∈O(2apa1

1pa2

provided

(1) β1∈Na1+1,

(2) p1=Fe0

1for 2e0

1∈Na−1and this p1∈P,

(3) q2=2a−2e

1Fa1+1−β1

1pa2

2+ 1 and such q2∈

(4) p1, q2satisfy equation 2apa1+1−β1

1pa2

(p1−1)(q2−1) and ϕ(m)=2apa1

1pa2

The set of such numbers mhas size at most a1+1.

If we consider the case ϕ−1(n)∈E(n)and clas-

sify such values of ϕ(n)by a quantity of prime mul-

tipliers, grater then 3 in ϕ(n).

Now we consider the statement about number of

solutions of equation ϕ(n) = 2mpα

1pβ

Theorem 4.4. If

ϕ(n) = 2mpα

1pβ

2,(6)

then maximal number of solutions n= 2 ·3pq sat-

isfying equation ϕ(pq)=2mpα

1pβ

2equals to m(α+

1)(β+ 1). The solutions have the following form:

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1−1pβ1

1pβ2

2+ 1 ∈P.

Proof. Since we search solutions for numbers of

the form n= 2k·3pq. The process of Eulers function

computation is determined by the formula:

ϕ2k3pq= 2k−1·2·(p−1) (q−1).

Implies that new non-zero power of 2 can contains

in p−1and q−1. But in our case k= 1. If we fix

that ϕ(n)=2mpα

1pβ

2, then structure of dividers of n

is the following:

m=m1+m2,

α=α1+α2, β =β1+β2

this follows from equations below

ϕ(n) = 2m·pα

1qβ

m=m1+m2,

α=α1+α2, β =β1+β2,

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1−1pβ1

1pβ2

2+ 1 ∈P,

n= 2 ·3pq.

The number of solutions of ϕ(n) = 2mpα

1pβ

2is de-

termined by number of partitions of m in 2 into terms

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

from 0 to m, and there are such C1

m+1 =m+ 1, but

the present factor 3 takes 1 term in the power, since

ϕ(3) = 2 of these two parts, so there are exactly m

possibilities for the number of partitions. The number

of partitions of the exponent αbetween powers [25] of

the factors pand qinto parts including the possibility

of an empty part is total, including a degenerate parti-

tion with an empty part. Entirely similarly, we obtain

the number of possible distributions of powers of the

number p2is equal to C1

β+1. The exact number of so-

lutions is determined by the number of cases when the

following two following conditions pertaining to set

of primе of the numbers pand qare satisfied.

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1−1pβ1

1pβ2

2+ 1 ∈P.

Verifying of the condition ϕ(3pq) = 2mpα

1pβ

2is pro-

viding with using of multiplicity of Euler’s function

ϕ(pq) = ϕ(p)ϕ(q). The proof is completed. Corol-

lary. In case of

n= 2pq,

if ϕ(n) = 2mpα

1pβ

2, (1) then maximal number of

equation solutions ϕ(pq) = 2mpα

1pβ

2equals to m(α+

1)(β+ 1). The solutions have the following form:

ϕ(n) = 2m·pα

1qβ

2, m =m1+m2,

α=α1+α2, β =β1+β2,

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1pβ1

1pβ2

2+ 1 ∈P.

The proof follows from proof of previous Theorem.

Remark 4.2. Minimal number of primes grater

then 3 in solution of (1) is possible if one of multipli-

ers factorized on powers of 2 and second multiplier

that is p2−1 = 2m2px

Proof. The special case arise, when p2−1 =

2m2px

1. This condition give us the next solution:

ϕ(n) = 2m·pα1

1, m =m1+m2,

p= 2m−m1pα1−x

1pα2−1

2+ 1 ∈P,

q=p2,

p2−1 = 2m1px

1;p1, p2∈P.

Then n=pq and ϕ(n) = 2mpα

1pβ

Secondly, it remains to consider the case m∈

O(2apa1

1pa2

2).

We consider the case ϕ−1(n)∈O(n)– odd num-

bers and classify such values of ϕ(n)by a quantity of

prime multipliers. grater then 3 in ϕ(n).

Theorem 4.4. (About number of solutions of

equation ϕ(n) = 2mpα

1pβ

2). If

ϕ(n) = 2mpα

1pβ

then maximal number of solutions n=pq satisfying

equation ϕ(pq) = 2mpα

1pβ

2equals to (m+ 1)(α+

1)(β+ 1). The solutions have in general case the fol-

lowing form:

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1pβ1

1pβ2

2+ 1 ∈P.

But in this case m=m1= 0.

Proof. Since we search first of all solutions for the

numbers n used in RSA algorithm then it are numbers

of the form n=pq. The process of Eulers function

computation is determined by the general formula for

n= 3pq:ϕ(3pq) = 2 ·(p−1) (q−1). Implies that

new non-zero power of 2 can contains in p−1and

q−1. If we fix that ϕ(n)=2mpα

1pβ

2, then structure

of dividers of nis the following: m=m1+m2, α =

α1+α2, β =β1+β2this follows from the equations

below

ϕ(n) = 2m·pα

1qβ

2, m =m1+m2,

α=α1+α2, β =β1+β2,

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1pβ1

1pβ2

2+ 1 ∈P.

where n=pq, p, q ∈P.

The number of solutions of ϕ(n) = 2mpα

1pβ

2is de-

termined by number of partitions of m in 2 into terms

from 0 to m, and there are such C1

m+1 =m+ 1, but

the present factor 3 takes 1 term in the power, since

ϕ(3) = 2 of these two parts, so there are exactly m

possibilities for the number of partitions. The num-

ber of partitions of the exponent αbetween powers of

the factors p and q into parts including the possibility

of an empty part is total, including a degenerate parti-

tion with an empty part. Entirely similarly, we obtain

the number of possible distributions of powers of the

number p2is equal to C1

β+1. The exact number of so-

lutions is determined by the number of cases when the

following two following conditions pertaining to set

of primе of the numbers pand qare satisfied.

p= 2m−m1−1pα1−β1

1pα2−β2

2+ 1 ∈P,

q= 2m1+1pβ1

1pβ2

2+ 1 ∈P.

Let’s check the condition ϕ(pq) = 2mpα

1pβ

2is carried

out taking into account the multiplicative property

of the Euler function ϕ(3pq) = ϕ(p)ϕ(q) =

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

(2 ·2m−m1−12pα1−β1

1pα2−β2

2)(2m1pβ1

1pβ2

2) =

2mpα1+α2

1pβ1+β2

2. Let’s notice, that p, q ∈Pas well

as their exponents as 3 adds another factor of 2.

Proposition 4.1 If ϕ(n)=2mpα

1pβ

2, then maxi-

mal number of solutions of the form n=pq satisfy-

ing equation ϕ(pq) = 2mpα

1pβ

2equals to (m+1)(α+

1)(β+ 1). Minimal number of primes grater then 2

in factorization of p−1and q−1is possible if one

of multipliers is

p= 2m−m1pα1−β1

1pα2−β2

2+ 1 ∈P

and second multiplier presents as p2−1=2m2px

Proof. The special case arise when p2−1 = 2m2px

gives us the result.

ϕ(n) = 2m·pα1

1, m =m1+m2,

p= 2m−m1pα1−x

1pα2−1

2+ 1 ∈P,

p2−1 = 2m1px

1;p1, p2∈P,

q=p2.

Then n=pq and ϕ(n) = 2mpα

1pβ

We now start to classify odd preimages.

Theorem 4.5. Let qβbe a divisor of x∈

φ−1(2apa1

1pa2

2),q∈P\ {2, p1, p2}. Then β= 1.

Proof. Let a= 2eqβm∈φ−1(2apa1pa2

2), where

e∈Wa, q is relatively prime to 2mand mis odd.

Then, 2apa1

1pa2

2= 2e−1qβ−1(q−1)φ(m). If β−1∈

N, then desired contradiction already arrived.

Theorem 4.6. If m∈O(2apa1

1pa2

2)then mcon-

tains at most anumber of odd prime divisors.

Proof. Let m∈O(2apa1

1pa2

2). Then m is odd and

evidently >3. Hence any prime divisor of mwill be

odd. Let the total number of such odd prime divisors

of mbe r. Then 2r|φ(m)i.e. 2r|2apa1

1pa2

2. In other

words, r∈Na.

We denote the total number of distinct prime fac-

tors of x∈Nby ω(x).

Theorem 4.7. If m∈O(2apa1

1pa2

2)and ω(m) =

1then mis one of the form

1. pa2+1

2provided p2= (2apa1

1+ 1) for case

2apa1

1+ 1 ∈Pholds,

2. q3, where q3= 2apa1

1pa2

2+ 1 for case

2apa1

1pa2

2+ 1 ∈P.

We are going to find out the explicit forms of x

when it is an odd element of the set ϕ−12apa1

1pa2

2. By

Theorem 4.5. r∈ {1,2, ..., a}, where ris a total num-

ber of odd prime divisor of x=m∈O(2apa1

1pa2

2).

We discuss each case of rone by one.

4.7.1 If r= 1. In this case, mwill be one of the

forms

(1) pβ1

1,β1∈N,

(2)pβ2

2,β2∈N,

(3)qβ3

3,β3∈N, where q3∈P\{2, p1, p2}

4.7.1.2 Futhermore if m=pβ1

1. Then

2apa1

1pa2

2=ϕ(pβ1

1) = pβ1

1(p1−1) yields

2apa1+1−β1

1pa2

2= (p1−1)

The number in left side is divisible by pa2

2but

the number in right side is not. Hence, this case is

rejected and so m6=pβ1

4.7.1.3 If m=pβ1

2, then

2apa1

1pa2+1−β2

2= (p2−1).(7)

It is evident, a2+ 1 −β1≥0. In other words,

β2∈Na2+1. If β2< a2+ 1 then previous equation 7

lead us to contradiction. So, β2=a2+ 1 and hence

2apa1

1= (p2−1) (8)

which implies that

(p2= 2apa1

1+ 1), and 2apa1

1+ 1 ∈P,(9)

if 2apa1

1+ 1 is prime indeed, only then it will be

taken under consideration as an eligible candidate in

the set ϕ−1(2apa1

1pa2

2).

Furthermore, equation (9) states if p2≡

1(mod3), p1≡0(mod3)and therefore p2=

2a3a1+ 1 and if 2a3a1+ 1 ∈PThus, m=pa2+1

2∈

O(2apa1

1pa2

2)provided (9) is satisfied equation.

4.7.1.4 m=qβ3

3. According to Corollary 4.3

β3= 1, therefore m=q3. By applying simi-

lar arguments as shown above, we shall get q3=

(2apa1

1pa2

2+ 1) ∈P. In order words, if 2apa1

1pa2

2+ 1

be a prime, it will be an element of

ϕ−1(2apa1

1pa2

2).

This completes the proof.

Example. Let Fa< Fbbe two distinct Fermat’s

primes and we consider the set ϕ−1(2FaFb). Here

it is a routine work to show Fb= 2Fa+ 1. So

b∈ϕ−1(2FaFb). Also, 2FaFb+ 1 = 0(mod 3).

Therefore, the cardinality of the set ϕ−1(2FaFb)is 0.

5 The cardinality of pre-totients for

ϕ(m).

We propose a exact formula for computing quantity

of the inverses of Euler’s function for any number of

form 2s.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

An old conjecture of Sierpinski asserts that for ev-

ery integer k > 2, there is a number m for which the

equation ϕ(t) = mhas exactly ksolutions the num-

ber of solutions tof ϕ(t) = m, also called the mul-

tiplicity of m. In this section we find multiplicity for

numbers of form 2s.

Example. The set of preimages for 12 is

following: φ−1(12) = {13,21,26,28,36,42}.

Also we have ϕ−1(16) = {32,48,17,34,40,60},

ϕ−1(18) = {19,27,38,54}. We remind, that the

number of a form 22n+ 1, where nis not-negative

integer, is called Fermat number.

Also the recursive formula for Fermat numbers

[13, 15, 18, 20] was used: Fn=F0...Fn−1+ 2. Be-

sides Useful for the study of the number of prototypes

is Lucas’s Theorem: each prime divisor of the Fermat

number Fn, where n > 1, has a form of k2n+2 + 1.

Lemma. If 2m+ 1 is prime, then m= 2n.

Proof. We will prove by contradiction. Suppose

there exists a number of a form 2m+ 1 which is

not prime and mis divisible by p6= 2. Since pis

prime and it is not 2, it must be odd. Let m=pt,

so we can rewrite our number like this: 2m+ 1 =

2tp+ (1)p=2t+ 12tp−1−... + (1)p−1.

Expressions in both brackets are grater than 1, but our

number is supposed to be prime. Contradiction.

We make of use Theorem about mutually primal-

ity of non-prime Fermat number [20].

Theorem 5.1. Let n∈N∪ {0}. If 22n+ 1 is not

prime, then for any number of the form 22n+a, where

a∈N,a < 2n, there exists exactly 2tnatural num-

bers msuch that ϕ(m) = 22n+a, where tis amount of

prime Fermat numbers, which are less than 22n+ 1.

Proof. Consider a set {p1, p2, ...pt}of all prime

Fermat numbers lesser than 22n+ 1. Let ϕ(x) =

22n+a. According to Lemma 1, x= 2sq1q2...qv,

where qiare different prime Fermat numbers. Since

a < 2n, then 22n+a<22n+1 . That means, that

qi<22n+1 + 1, because ϕ(x) = ϕ(2sq1q2...qv) =

22n+a<22n+1 .

We also know that qi6= 22n+ 1, because 22n+ 1

is not prime. This yields qi<22n+ 1. Other

words it can be written like this: {q1, q2, ...qv} ⊆

{p1, p2, ...pt}. For each xwe get, that {q1, q2, ...qv}

is a subset of the set {p1, p2, ...pt}. We shall prove,

that each subset of the set Mt={p1, p2, ...pt}deter-

mines such unique xas a unique product of this subset

of primes from Mt, that xwith a corresponding mul-

tiplier 2s, s ∈N∪ {0}gives us x= 2stsuch that

ϕ(x) = 22n+a.

For this goal we need to show, that

ϕ(p1·p2·...pt)<22n+a.

Since ϕ(p1·p2·...pt)is Euler’s function of a

product of prime Fermat numbers, which lesser than

22n+ 1, it is not grater than value of Euler’s function

of a product of all Fermat numbers, which lesser than

22n+ 1, which is equal to

ϕ220+ 1... 22n−1+ 1.

That is true, as obvious inequality holds: ϕ(d)≤

ϕ(db). It is also known, that any two Fermat numbers

are coprime [20], so

ϕ220+ 1... 22n−1+ 1 =

=ϕ220+ 1...ϕ 22n−1+ 1.

As known, ϕ(y)≤y−1, therefore

ϕ220+ 1...ϕ 22n−1+ 1≤

≤220+ 1 −1·... ·22n−1+ 1 −1=

= 20·... ·22n−1= 22n−1.

It was used the formula of the sum of geometric pro-

gression, we have 20+ 21+... + 2n−1= 2n−1.

Therefore 220+ 1 −1·.. ·22n−1+ 1 −1=

220+21+..+2n−1= 22n−1.

Finally,

ϕ(p1·p2·...pt)≤22n−1<22n+a,

what was needed. That means, that Euler’s function

of the product of the elements of any subset of the

set {p1, p2, ...pt}is lesser than 22n+a. Let us take

an arbitrary subset of {p1, p2, ...pt}. Let the elements

of this set be {q1, q2, ...qv}. Consider the expression

ϕ(q1·q2·... ·qv) = 2w<22n+a. This inequality

means, that we can choose such natural number s,

so ϕ(2s·q1·q2·... ·qv)=2s−1·2w= 22n+a. In

other words, for given subset {q1, q2, ...qv}, we found

such number x, that ϕ(x) = 22n+a. The last equality

means, that each subset defines unique x.

Therefore, each subset gives us the needed the

number xthat is always determined by some sub-

set. In other words, the amount of needed numbers is

exactly the amount of different possible subsets. As

well-known fact, this amount is equal 2tfor a set of t

elements.

Example. For a non-prime Fermat number 232+1,

number of preimages for subsequent numbers of the

form 22n+a, a ≤32 −1, n ≤4is equal to 232.

For generalizing of Theorem 5.1 it is convenient

to prove the following statement:

Theorem 5.2 Let a∈Z, 0≤a≤2n, then the

number of solutions of ϕ(x)=22n+ais equal to the

number of sets {2i1, ..., 2ik}, such that: i1< i2<

... < ik

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

2i1+ 2i2+... + 2ik≤2n+a,

22i1+ 1, ..., 22ik+ 1 ∈Fpr,

where Fpr is a set of Ferma’s prime numbers.

If 22n+1 is not prime, then the number of specified

sets (including empty set) is equal to 2t, where tis a

number of Ferma’s prime numbers smaller then 22n+

Proof. To construct the necessary preimage xover

the set of Ferma’s primes with the properties of this

Theorem ϕ(x) = 22n+awe proceed as follows:

1) We choose a combination of this numbers. Let

us call it

22i0+ 1...22ik−1+ 1.

2) Then we should find its total power of 2 that

is 2i1+ 2i2+... + 2ik=s, this power be ob-

tained after calculating the Euler’s function from the

product ϕ22i0+ 1...22ik+ 1 and also satis-

fies the inequality

s= 2i1+ 2i2+... + 2ik≤2n+a.

We supplement the received power exponent sto

the necessary 2n+aby multiplying the product of

22i0+ 1...22ik+ 1

on 22n+a−s. Thus, the necessary preimage xis

constructed.

Property. For any number Sof the form

pα1

1pα2

2... pαk

k, p1>2, where p1, p2, ... , pkare odd

prime numbers, the following equality holds: ϕ(S) =

ϕ(2S).

Proof. Since 2 and pα1

1pα2

2... pαk

k, p1>2are co-

prime, then

ϕ2pα1

1pα2

2... pαk

k=ϕ(2) ϕpα1

1pα2

2... pαk

k=

=ϕpα1

1pα2

2... pαk

k.

Therefore these numbers has the same of Euler’s

function.

6 The lower bound for ϕ−1(m).

We suggest a lower bound estimate for computing

quantity of the inverses of Euler’s function. Our ap-

proach can be further adapted for computing certain

functions of the inverses, such as their quantity, the

larger.

Definition 6.1 Let Mkbe a set of first kconsecu-

tive primes. We will say, that the number is decom-

posed over a set Mk, if in its canonical decomposition

there are only numbers from Mk. Let x1, ... , xn+2

be such numbers, that ϕ(x1) = ϕ(x2) = ... =

ϕ(xn+2), and at the same time all prime factors of

the canonical decomposition belong to the set Mn=

{p0, ...., pn}, where p0= 2 and piare all consecutive

prime numbers. Let for any natural number n,we de-

fine Qn= (p0−1) (p1−1) ... (pn−1−1) (pn−1),

where piis i-th odd prime number, where i∈Nand

p0= 2.

Example: p1= 3, p2= 5, p3= 7,

then Q3= (p0−1) (p1−1) (p2−1) (p3−1) =

(3 −1) (5 −1) (7 −1) = 48.

So the first presentation of 48 over M3has canon-

ical form ϕ(3 ·5·7) = 2 ·22·2·3 = 48,and

rest 4 presentations of 48 over M3are the following:

ϕ(24·32) = 23·3·2 = 48,

ϕ(5 ·9·22) = 3 ·24= 48,

ϕ(7 ·5·2) = 3 ·24= 48,

ϕ(7 ·24) = 3 ·24= 48,

thus, we obtain 5 presentations for Q3.

Let Mkbe a set of kconsequent first prime num-

bers. The following statement about estimation of

pre-totients number is true.

Theorem 6.1 For each natural n∈Nthere is a set

of such various natural numbers

x1,x2, ..., xn,xn+1,xn+2, that

ϕ(x1) = ϕ(x2) = ... =ϕ(xn+2) = Qn,

where every number xicontains in its canonical de-

composition [20] only pifrom Mn(i.e. pi< pnif

i < n), and

xn+2 =p0p1... pn−1pn

holds.

Proof. We prove it by the mathematical induction.

Base case: given n= 1, then P1= (p1−1) = 2

has at least three preimages. This statement is true,

because ϕ(3) = ϕ(4) = ϕ(6) = 2 = Q2. The base

case is proved.

Step case: if for n=kit holds, we will prove,

that for n=k+ 1 it holds too. By the assumption

we have, that for natural number nwere found such

various natural x1,x2, ...,xk+1,xk+2, that

ϕ(x1) = ϕ(x2) = ... =ϕ(xk+1) =

=ϕ(xk+2) = Qk=Q,

where Qk=pβ0

0pβ1

1... pβk

xk+1 =p1p2...pk−1pk, xk+2 =p0p1p2...pk−1pk.

Let us make induction transition. Prove, that for n=

k+ 1 exist such various natural y1,y2,...,yk+2, yk+3,

for which holds:

ϕ(y1) = ϕ(y2) = ... =

=ϕ(yk+2) = ϕ(yk+3) = Qk+1,(10)

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

each of which has a canonical decomposition over

Mk∪pk+1. Clear, that ϕ(pk+1)has a canonical de-

composition into elements of Mkbecause of all pre-

vious primes are in Mkand ϕ(pk+1)< pk+1.

Therefore, it can be presented as

ϕ(pk+1) = pβ0

0pβ1

1... pβk

Let’s construct new numbers

y1,y2, ... ,yk+1,yk+2,yk+3 in such a way:

y1=x1pk+1, y2=x2pk+1, ... ,yk+1=

=xk+1pk+1, yk+2=xk+2pk+1.

In this case, the value of the Euler function

is Qk+1 =pβ0

0pβ1

1... pβk

k.Let us show, that all

y1, ... ,yk+2, yk+3 are different.

Since numbers x1,x2, ...,xk+1,xk+2 from (1) have

different canonical decompositions, so the decompo-

sitions of numbers y1,y2, ... ,yk+1,yk+2 over Mkare

different too, but they all have a new factor pk+1, but

do not decompose over Mk. A last one yk+3 also

decomposes over Mkand does not contain a factor

pk+1. But value Qk+1 =pβ0

0pβ1

1... pβn

ndoes not con-

tain pk+1 in the decomposition, so there is at least one

number yk+3 with decomposition over Mk, such, that

ϕ(yk+3) = Qk+1 holds.

Since Qk+1 > Qk, then a new preimage

yk+3 does not coincide with any of the numbers

y1,y2, ...,yk+1,yk+2 which give the value of Euler’s

function equal Qk.

Moreover such yk+3 can be not unique number

that can be constructed over Mksuch, that ϕ(yk+3) =

Qk+1. Consequently beyond y1,y2, ... ,yk+1,yk+2,

which decomposed over Mk+1, we have at least one

new yk+3, which can be decomposed over Mkin

product of primes. Thus Qk+1 has at least k+ 3 dif-

ferent preimages.

We propose method of constructing of such pre-

totients set.

Let p0= 2, p1= 3, p2= 5, . . . , pnbe consecu-

tive prime numbers, where n=k+ 1. Note, that

ϕ(p0p1, . . . , pn)=(p0−1)(p1−1)...(pn−1).

Let us construct some new numbers x0, . . . , xn, for

which ϕ(x0) = ϕ(x1) = ... =ϕ(xn) =

ϕ(p0, p1, . . . , pn)=(p0−1)(p1−1)...(pn−1).

Namely, let

x0= (p0−1)p0, . . . , pn,

x1=p0(p1−1)p2, . . . , pn,

· · ·

xn=p0p1, . . . , pn−1(pn−1−1).

Now we will prove, that ϕ(p0p1...pk−1(pk−

1)pk+1...pn)=(p0−1)(p1−1)...(pn−

1) for every k∈ {0,1, ..., n}. Obviously,

p0...pk−1(pk−1) and pk+1...pnare coprime, so

ϕ(xk) = ϕ(p0p1...pk−1(pk−1)) ×ϕ(pk+1 . . . pn) =

ϕ(p0p1...pk−1(pk−1)) ×(pk+1 −1)...(pk−1). That

is, we have to prove the equality ϕ(p0p1...pk−1(pk−

1)) = (p0−1)(p1−1)...(pk−1).

Let for induction step yk+3 =xk+2(pk+1 −1).

Since only p0p1, . . . , pk−1are the prime numbers,

which are not more than (pk−1), we have pk−

1 = α0α1, . . . , αk−1for some non-negative integer

α0α1, . . . , αk−1.

By direct calculation we ob-

tain ϕ(p0p1...pk−1(pk−1)) =

ϕ(pα0+1

0pα1+1

1...pαk−1+1

k−1) =

(p0−1)...(pk−1−1)p(α0+1)−1

0...p(αk−1+1)−1

k−1=

= (p0−1)(p1−1)...(pk−1−1)pα0

0...pαk−1

k−1=

(p0−1)(p1−1)...(pk−1−1)(pk−1).

Also we may subtract 1 from more than one pk, if

(pk−1) has the decomposition into prime factors,

which does not contain some pj,(j < k). For exam-

ple, ϕ(p0p1p2p3) = ϕ(2 ×3×5×7) = 48. Except

(2−1)×3×5×7,2×(3−1)×5×7,2×3×(5−1)×7

and 2×3×5×(7 −1), we may take as preimage, for

example, 2×(3 −1)(5 −1) ×7, because (3 −1) = 2

and (5 −1) = 22. Hence ϕ(2 ×(3 −1)(5 −1)) =

(2 −1)(3 −1)(5 −1) by the same arguments, as for

p0, . . . , pk−1(pk−1)pk+1, . . . , pn. So, we may con-

struct at most 2nproducts of the form p0q1, . . . , qn,

where qk=pk. Also (p0−1)p1, . . . , pnfits for the re-

quirement ϕ(p0−1)p1, . . . , pn= (p0−1)...(pn−1),

so we have at most 2n+ 1 numbers, which give us

the same meaning of ϕ, as p0, . . . , pn. Note, that it

is not necessarily the complete set of such numbers

x, for which ϕ(x) = p0p1, . . . , pn, but it is the set,

which may be obtained by the given by us scheme.

The case when a number of form f(m)is prime

we denote by (f(m))p. We denote Mersenne number

by Mm, where Mm= 2m−1.

Corollary. If Ma< Mbfor m∈N, then set

ϕ−1(2MaMb)contains an element M2

bif and only

if b=a+ 1. On the other hand, if 2MaMb+ 1 ∈

Pthen ϕ−1(2MaMb)⊆ {{2M2

b,2(2MaMb+ 1)P,

b,(2MaMb+ 1)P};a+ 1 = b} ∪

∪ {{2(2MaMb+ 1)P,(2MaMb+ 1)P};a+ 1 6=b}.

7 Possible questions for further

research.

For an introduction, interested reader can refer [10]

for further study, from which we collect some of the

important properties of ϕ(n).ϕ(m)=2ak

i=1

pai

8 Conclusion.

The analytic expression for exact multiplicity of in-

verses for m= 22n+a, where a∈N,a < 2nand

ϕ(t) = mwas obtained. As it turned out, it de-

pends on the number of prime numbers Fermat. The

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022

method of constructing of preimages set for obtained

by us lower bound was proposed by us. These results

can be applied not only to the cryptanalysis of cipher

RSA [24] and in the coding theory [21]. The author

is grateful to Volodya Karlovskyi for correcting re-

marks.

References:

[1] Kevin Ford, The Number of Solutions of ϕ(x) =

mAnnals of Mathematics, Second Series, Vol.

150, No. 1 (1999), P. 283-312.

[2] Coleman, R., On the image of Euler’s Totient

Function, http://arxiv.org/pdf /0910.2223v1.pdf

[3] Gupta, Hansraj, Euler’s Totient Function and

Its Inverse, Indian Journal of Pure and Applied

Mathematics, 12(1), January 1981, 22-30

[4] On Euler’s Phi Function, R.D.Carmichael

[5] FermatSearch.org, http://fermatsearch.org

[6] Keller, Wilfrid, Prime Factors of Fermat Num-

bers, http://www.protsearch.net/fermat.html

[7] Weisstein. Eric W., Fermat Number, http://math-

world.wolfram.com/FermatNumber.html

[8] http: //numbertheory.org/php/carmichael.html

[9] Tsang, Cindy, Fermat Numbers, M414 Number

Theory

[10] http://prothsearch.net/fermat.htmlSurnmary

[11] Burton, David, Elementary Number Theory,

McGraw Hill Education(India) Private Limited,

2012.

[12] Skuratovskii, Ruslan. On Investigation of

Euler’s Totient Function Preimages, (2019).

https://arxiv.org/abs/1812.00067

[13] Michal Kevek, Florian Luca, Lawrence Somer

17 Lectures on Fermat Numbers: From Number

Theory to Geometry, Springer, CMS Books 9,

ISBN 0-387-95332-9.

[14] Rodney Coleman On the image of Euler’s totient

function. Journal of Computer mathematics Sci.

(2012), Vol.3 (2), P. 185-189.

[15] Ruslan Skuratovskii, ”The investigation of Eu-

ler’s totient function preimages” Sixth Interna-

tional Conference on Analytic Number Theory.

Voronoy Conference” Book of abstracts. P. 37-

39.

[16] R. V. Skuratovskii. On commutator subgroups

of Sylow 2-subgroups of the alternating group,

and the commutator width in wreath products. /

Ruslan V. Skuratovskii // European Journal of

Mathematics. vol. 7: 1. (2021), P. 353-373.

doi.org/10.1007/s40879-020-00418-9.

[17] Ruslan V. Skuratovskii, Aled Williams Irre-

ducible bases and subgroups of a wreath product

in applying to diffeomorphism groups acting on

the Möbius band. Rendiconti del Circolo Matem-

atico di Palermo Series 2. 2020, V. 70, pp. 351-

364.

[18] R. V. Skuratovsky, Corepresentation of a sy-

low p-subgroup of a group Sn. Cybernetics

and Systems Analysis 2009. 45(1), pp. 25-37.

https://doi.org/10.1007/s10559-009-9080

[19] R. Skuratovskii, The Derived Subgroups of Sy-

low 2-Subgroups of the Alternating Group and

Commutator Width of Wreath Product of Groups.

Mathematics, Basel, Switzerland, (2020) № 8(4),

pp. 1-19.

[20] Ivan Vinogradov, Elements of Number Theory

Dover Publications, 5th ed. 2016. P. 236.

[21] R.V Skuratovskii. A method for fast

timer coding of texts”. Cybernetics and

Systems Analysis. 2013. 49 (1), 133-138.

https://doi.org/10.1007/s10559-013-9493-4

[22] Osadchyy, V., Skuratovskii, R. Criterions of su-

persinguliarity and groups of Montgomery and

Edwards curves in cryptography. WSEAS Trans-

actions on Mathematics 19, 2020. pp. 709-722.

[23] Skuratovskii, R., Osadchyy, V. The order of Ed-

wards and Montgomery curves WSEAS Transac-

tions on Mathematics. 19, 2020. pp. 253-264.

[24] Buhler, J. Lenstra, H. Pomerance, Carl.

(2006). Factoring integers with the number field

sieve. 10.1007/BFb0091539.

[25] Nongluk Viriyapong, Chokchai Viriyapong On

the Diophantine Equation nx+ 13y=z2where

n= 2(mod39) and n+1 is not a Square Number,

WSEAS Transactions on Mathematics, vol. 20,

pp. 442-445, 2021.

Contribution of individual authors to

the creation of a scientific article

(ghostwriting policy)

This is the monic paper

Follow: www.wseas.org/multimedia/contributor-

role-instruction.pdf

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.7

Ruslan Skuratovskii

E-ISSN: 2224-2880

Volume 21, 2022