Unit - 2

Number theoretic functions

2.1 Number theoretic functions

The product of the values of these functions at two reasonably prime integers equals the product of the values of the functions at these integers. We begin by proving a few multiplicative function theorems that we will utilise later. Then we look at special functions and show that the previously seen Euler -function is truly multiplicative. The sum of divisors and the number of divisors functions are also defined. Define the Mobius function afterwards, which looks at integers in terms of their prime decomposition. The sum of the values of ff at the divisors of a given integer nn is the summatory function of a given function. The Mobius inversion of this function is then found, which writes the values of ff in terms of the summatory function's values. We will conclude this chapter by presenting integers with intriguing features and proving some of them.

The set N of positive integers is the domain of definition for an arithmetic function.

An arithmetic function ff is called multiplicative if f(ab)=f(a)f(b) for all a,b∈N such that (a,b)=1.

An arithmetic function ff is called completely multiplicative if

f(ab)=f(a)f(b)(4.1.1)

For all positive integers a,b.

The function f(a)=1 where kk is a completely multiplicative function since

f(ab)=1=f(a)f(b).(4.1.2)

It's also worth noting that a fully multiplicative function is a multiplicative function, but not otherwise.

We'll now show a multiplicative function theorem. The features of multiplicative functions, rather than entirely multiplicative functions, will be of importance to us.

Given a multiplicative function f. Let n=∏sk=1pakk spkak be the prime factorization of n. Then

f(n)=∏k=1sf(pakk).(4.1.3)

By induction on the number of primes in the factorization of nn, we prove this theorem. Assume that n=pa1. As a result, the outcome is straightforward. Assume for a moment that

n=∏k=1spakk,(4.1.4)

We have

f(n)=∏k=1sf(pakk).(4.1.5)

So we have to prove that if

n=∏k=1s+1pakk,(4.1.6)

Then

f(n)=∏k=1s+1f(pakk).(4.1.7)

Notice that for

n=∏k=1s+1pakk,(4.1.8)

We have (∏sk=1pakk,pas+1s+1)=1(∏k=1spkak,ps+1as+1)=1.

Thus we have get

f(n)=f(∏k=1s+1pakk)=f(∏k=1spakk)f(pas+1s+1)(4.1.9)

Which by the inductive step gives

f(∏k=1s+1pakk)=f(n)=∏k=1s+1f(pakk).(4.1.10)

We can see from the preceding theorem that knowing the value of a multiplicative function at the primes in the prime factorization of a number will suffice to evaluate it at an integer.

We now develop summatory functions, which reflect the sum of a function's values at a particular number's divisors.

Consider the arithmetic function f.

Define

F(n)=∑d∣nf(d)(4.1.11)

F is thus referred to as the summatory function of f.

This function returns the sum of the arithmetic function's values at a specified integer's divisors.

If f(n) is an arithmetic function, then

F(18)=∑d∣18f(d)=f(1)+f(2)+f(3)+f(6)+f(9)+f(18).(4.1.12)

If f is a multiplicative function, then the summatory function of f denoted by F(n)=∑d∣nf(d) is also multiplicative.

We have to prove that F(mn)=F(m)F(n) whenever (m,n)=1. We have

F(mn)=∑d∣mnf(d).(4.1.13)

Each divisor of mn can be expressed uniquely as a product of relatively prime divisors d1 of m and d2 of n, and the product of any two divisors of m and n is a divisor of mn, according to Lemma 6. As a result,

F(mn)=∑d1∣m,d2∣nf(d1d2)(4.1.14)

Notice that since f is multiplicative, we have

F(mn)===∑d1∣m,d2∣nf(d1d2)∑d1∣m,d2∣nf

(d1)f(d2)∑d1∣mf(d1)∑d2∣nf(d2)=F(m)F(n)

Key takeaways:

• Number theorists study the properties of integers, which are the natural numbers -1, -2, 0, 1, 2, and so on.

• Number theory is known as "The Queen of Mathematics" because of its central role in the science.

2.2 Sum and number of divisors

2.2.1 Number of divisors

The prime factorization of a divisor d must be a subset of the prime factorization of nn, for example, 6=23 is a divisor of 60=22355. So all we have to do now is find all the different subsets of n's prime factorization.

For a collection of x elements, the number of subsets is usually 2x. If the set contains repeated entries, however, this is no longer the case. Some prime factors may appear more than once in the prime factorization of n in our situation.

We can utilise the factor pp up to e times in the subgroup if a prime factor p appears e times in the prime factorization of nn. As a result, we have e+1 options.

As a result, if n's prime factorization is pe11pe22pekk, with pipi being separate prime integers, the number of divisors is:

d(n)=(e1+1)⋅(e2+1)⋯(ek+1)

A way of thinking about it is the following:

• If n=pe11n=p1e1 is the sole distinct prime divisor, then there are e1+1 divisors (1,p1,p21,...,pe11).

• If there are two distinct prime divisors, n=pe11pe22, then all divisors can be arranged in a tabular format.

	1			…
1	1			…
				…
				…
:	:	:	:		:
				…

• So the number of divisors is trivially (e1+1)⋅(e2+1)
• A similar argument can be made if there are more then two distinct prime factors.

2.2.2 Sum of divisors

The argument from the previous section can be utilised again.

The sum is: n=pe11 if there is just one distinct prime divisor.

If there are two distinct prime divisors n=pe11⋅pe22, then we can make the same table as before. The only difference is that now we now want to compute the sum instead of counting the elements. It is easy to see, that the sum of each combination can be expressed as:

• For n=pe11pe22pekk, we get the following formula:

2.3 Totally multiplicative '-1’

Multiplicative Functions

An arithmetical function, or number-theoretic function is a complex-valued function defined for all positive integers. It can be viewed as a sequence of complex numbers.

Examples: n!,ϕ(n),π(n) which denotes the number of primes less than or equal to n.

If f(mn)=f(m)f(n) whenever gcd(m,n)=1, an arithmetical function is multiplicative, and if this holds for any m,n, it is entirely multiplicative or completely multiplicative. Thus, unless f is the zero function, f(1)=1, and the behaviour of a multiplicative function on prime powers is totally specified.

Examples: We saw that the Euler totient function is multiplicative but not completely multiplicative (which is why (1)=1) is useful). n2 is a completely multiplicative function. It is (completely) multiplicative to combine (totally) multiplicative functions.

Theorem: Let f(n) be a multiplicative function, and define

F(n)=∑d|nf(d).

Then F(n) is also a multiplicative function.

Proof: Let m,n be positive integers with gcd(m,n)=1. Then

F(mn)=∑d|mnf(d)=∑r|m,s|nf(rs)=∑r|m,s|nf(r)f(s)=∑r|mf(r)∑s|nf(s)=F(m)F(n)

Since r|m and s|n implies (r,s)=1.

We just wrote F(n) in terms of f(d). Can we do the reverse? That is, write f(n) in terms of F(d)? Yes; this is known as Möbius inversion.

Since ϕ is multiplicative, we have that

Theorem:

∑d|nϕ(n)=n

This theorem can also be proved using basic facts about cyclic groups.

Examples:

1) The divisors of 12 are 1,2,3,4,6,12. Their totients are 1,1,2,2,2,4 which sum to 12.

The function f(n)=1 is (totally) multiplicative. Let d(n) be the number of divisors of n. Then since d(n)=∑d|n1 we see that d(n) is multiplicative.

The function f(n)=n is (totally) multiplicative. Let σ(n) be the sum of divisors of n. Then since σ(n)=∑d|nn we see that σ(n) is multiplicative. In general, we can apply this trick to any power of n.

2) n!,ϕ(n),π(n) which denotes the number of primes less than or equal to n.

Solution:

If f(mn)=f(m)f(n) whenever gcd(m,n)=1, an arithmetical function is multiplicative, and if this holds for any m,n, it is entirely multiplicative or completely multiplicative. Thus, unless f is the zero function, f(1)=1, and the behaviour of a multiplicative function on prime powers is totally specified.

3) The divisors of 12 are 1,2,3,4,6,12. Their totients are 1,1,2,2,2,4 which sum to 12.

Solution:

The function f(n)=1 is (totally) multiplicative. Let d(n) be the number of divisors of n. Then since  we see that d(n) is multiplicative.

The function f(n)=n is (totally) multiplicative. Let σ(n) be the sum of divisors of n. Then since  we see that σ(n) is multiplicative. In general, we can apply this trick to any power of n.

2.4 Functions, definition and properties of the Dirichlet product

2.4.1 Definition

If {\displaystyle f,g:\mathbb {N} \to \mathbb {C} }  are two arithmetic functions from the positive integers to the complex numbers, the Dirichlet convolution f ∗ g is a new arithmetic function defined by:

Where the sum encompasses all positive divisors d of n, or alternatively, all different pairs (a, b) of positive integers whose product is n.

The study of Dirichlet series, such as the Riemann zeta function, naturally produces this product. In terms of their coefficients, it explains the multiplication of two Dirichlet series.

2.4.2 Properties

Under pointwise addition, the set of arithmetic functions forms a commutative ring, the Dirichlet ring, with f + g defined as (f + g)(n) = f(n) + g(n), and Dirichlet convolution. The unit function (n) = 1 if n = 1 and (n) = 0 if n > 1 is the multiplicative identity. The arithmetic functions f with f(1) 0 are the ring's units (invertible elements).

Specifically, Dirichlet convolution is associative,

Distributes over addition

Is commutative,

And has an identity element,

Furthermore, for each {\displaystyle f}f having {\displaystyle f(1)\neq 0} , there exists an arithmetic function {\displaystyle f^{-1}} with {\displaystyle f*f^{-1}=\varepsilon } , called the Dirichlet inverse of {\displaystyle f}f.

Every not-constantly-zero multiplicative function has a Dirichlet inverse that is also multiplicative, and every not-constantly-zero multiplicative function has a Dirichlet inverse that is multiplicative. In other words, multiplicative functions are a subgroup of the Dirichlet ring's invertible elements. However, keep in mind that the product of two multiplicative functions is not a multiplicative function. (since {\displaystyle (f+g)(1)=f(1)+g(1)=2\neq 1} , As a result, the subset of multiplicative functions is not a Dirichlet ring subring. Several convolution relations among major multiplicative functions are listed in the article on multiplicative functions.

Pointwise multiplication is another arithmetic function operation: fg is defined by (fg)(n) = f(n) g. (n). Pointwise multiplication by h distributes across Dirichlet convolution for a totally multiplicative function h:  Convolution of two totally multiplicative functions is multiplicative, though not always.

2.4.3 Functions

The following is a complete list of commonly studied arithmetic functions:

Arithmetic functions is a category of arithmetic functions.

The following are a few of the most important:

• The identity element for Dirichlet product: Denoted I, this is the indicator function for : it is 1 at 1 and 0 elsewhere.
• The all ones function: This function sends everything to 1. This is denoted by U. Note that although this is the identity for pointwise multiplication, it is not the identity for the Dirichlet product.
• The Mobius function: Denoted , this is the inverse of the all ones function with respect to the Dirichlet product.
• The identity function: This function sends every natural number to itself, now viewed as a ring element. This is denoted E. Although this would be the identity for composition, it is not the identity for the Dirichlet product.

Examples:

1) Show that the Dirichlet inverse of λ is ∣μ∣.

Solution:

Both λ and ∣μ∣ are multiplicative, so their Dirichlet convolution λ∗∣μ∣ is multiplicative.

As a result, e is also multiplicative, hence demonstrating that the two functions agree on prime powers is sufficient. (The article on multiplicative functions explains this crucial fact.)

Now,

Since e(pk)=0, the functions agree on prime powers and hence are the same.

2) Show that d∗φ=σ.

Solution:

Start with 1∗φ=I and convolve both sides with 1:

3) Show that

Solution:

The left side is

Where φ=μ∗I comes from Möbius inversion of φ∗1=I. Rearranging and moving parentheses around gives

And

2.5 The Mobius inversion formula

Suppose for some (not necessarily multiplicative) number-theoretic function f

F(n)=∑d|nf(d).

Can we make f(n) the subject of this equation?

We’ll see that we can find a function μ such that

f(n)=∑d|nμ(n/d)F(d)=∑d|nμ(d)F(n/d).

And we call this process Möbius inversion.

We have

∑d|nμ(d)F(n/d)=∑d|nμ(d)∑r|ndf(r)=∑dr|nμ(d)f(r)=∑r|nf(r)∑d|(n/r)μ(d)

If we want this equal to f(n) we need μ to satisfy

∑d|mμ(d)={0,m>11,m=1

A little thought leads to this unique solution, known as the Möbius function:

μ(n)={1n=10p2|n for some prime p(−1)rn=p1...pr for distinct primes pi

Notice μ is multiplicative, which implies f(n) is multiplicative if F(n) is. In summary,

Theorem:

F(n)=∑d|nf(d)

If and only if

f(n)=∑d|nμ(n/d)F(d)

And f(n) is multiplicative if and only if F(n) is multiplicative.

Example: From before n=∑d|nϕ(n). Write n=p1k1...pmkm. Then

ϕ(n)=∑d|nμ(d)nd=n∑d|nμ(d)1d=n(1−∑i1pi+∑i≠j1pipj−...)=n(1−1p1)...(1−1pm)

Which is another way to derive the formula for ϕ.

Gauss encountered the Möbius function over 30 years before Möbius when he showed that the sum of the generators of Zp∗ is μ(p−1). More generally, if Zn∗ has a generator, then the sum of all the generators of Zn∗ is μ(ϕ(n)). This can be seen by considering the sums of the roots of polynomials of the form xd−1 where d|ϕ(n).

Key takeaways:

If n>1 and d|n(d)=0, the Möbius function is a multiplicative arithmetic function. It appears in inversion formulas (see, for example, the Möbius series) and is employed in the study of other arithmetic functions.

2.6 The greatest integer function

2.6.1 What is the greatest integer function?

A function that returns a constant number for each specific interval is known as the biggest integer function. An open and closed bracket, [ ], is commonly used to symbolise these functions. These are the integer values of the expression inside the brackets, rounded down. The biggest integer functions are illustrated in the following examples:

• $f(x) = [ -5.678]$
• $g(x) = [-x + 1]$
• $h(x) = [-4x2 – 5]$

We'll find the number's maximum integer value when the expression inside the brackets is only a constant.

2.6.2 How to find the greatest integer value?

Let's start by figuring out how to find the largest integer value of a given number. When looking for the largest integer values, keep the following two rules in mind:

If the number in the brackets is not an integer, the smaller integer closest to the supplied number is returned.

• For example, if we have $f(x) = [-15.698]$, the two closest integers are $-16$ and $-15$. For the greatest integer values, we always choose the smaller integer. This means that $[-15.698] = -16$.

We return the original number if the number inside the brackets is an integer.

• This means that if we have g(x) = [48], the greatest integer value is equal to .

Here are some more examples of the greatest integer values:

Once we've mastered finding the largest integer values, we can use that knowledge to graph the largest integer functions. We'll study why this function is also known as a step function in the next section of this essay.

2.6.3 How to graph greatest integer function?

It's time to learn how to provide the biggest integer function on a $xy$-coordinate system. When graphing any other function, we use the same procedure:

• Create a table of values that meets the function's requirements.

• Draw a graph with these points.

• To construct the function, connect the points with a line or a curve.

But what distinguishes the biggest integer or step function from others? As open and closed points, we're using intervals and endpoints.

• On the smaller integer, there will be a shaded point, and on the larger integer, there will be an unfilled dot.

• Vertical lines will then connect each of these.

• For each interval, the same procedure will be followed.

Let's start by graphing [f(x) = [x]], which we can do by making a table of data first.

We may plot each open and closed dot now that we know the values for each interval. After that, draw a line between each pair of dots. The interval [[0, 1)] will be plotted as follows:

2.6.4 Summary of the greatest integer function definition

We now know everything there is to know about the biggest integer function, including its fundamental definition, attributes, and graph.

In the next section, we'll begin working on more complex issues, but first, let's review everything we've learned so far:

• We can use the largest integer functions (also known as step functions) to locate the lower integer value that is near to a given number.

• The graph of the step function can be determined by finding values of at specific intervals of

• The graph of the biggest integer functions resembles a staircase step.

• We can graph different functions using the graph of f(x) = [x].

Numericals:

1) Find the value of x such that ⌊x+3⌋ = 3

Solution:

From the definition of the greatest integer function, we have 3 ≤ x+1 < 4

Subtract 1 in this inequality.

We get, 2 ≤ x < 3

Answer: x can have values less than 3 and larger than or equal to 2.

2) The domain of the following biggest integer functions is:

a) f(x)=1/⌊x⌋

(b) g(x)=1{x}?

Solution:

(a) The denominator should not be 0, that is, ⌊x⌋≠0

If a number is in the interval [0,1), the biggest integer portion of that number is 0.

As a result, this interval must be eliminated from the set of real numbers in order to obtain the domain.

This means that the domain of f is R−[0,1)

(b) Once again, the denominator should not be 0, which means that {x}≠0

When is the fractional part of a number equal to 0?

Only when that number is an integer!

Thus, the domain of g is R−Z, that is, all integers have been excluded from the set of real numbers.

Answer: The domain of f is R−[0,1) and the domain of g is R−Z.

3) Which of the following cannot be the value of [ 3√1 ] + [ 3√2 ] + [ 3√3 ] + ........+ [ 3√n > ] ?

Solution: 

Breaking the problem into steps,

Because the cube of 2 is 8, the value of [ 3√1 ]is 1 and will remain so until [ 3√7 ], hence [ 3√8 ]= 2. As a result, the sum of the first seven terms is seven.

Each phrase from [ 3√8 ] through [ 3√26 ]  has a value of 2. These 19 terms add up to a total of 38. The total of all 26 terms is 7 + 38 = 45.

It also suggests that the sum of these terms for 7 < n < will be 7 + 2k. That means the total 37, which exists exclusively in this form, is unquestionably conceivable. As a result, the first option is viable.

Each of the 37 terms has a value of 3 from [ 3√27 ]  to [ 3√63 ], for a total of 111. Up to this point, the total is 156. As a result, 153 is also a possibility.

Now, [ 3√64 ]= 4, and each of the next 61 words will have a value of 4. For n > 63, this indicates the sum will be 156 + 4k.

Now, 188 is a number of this kind that is conceivable, however 190 is not because it cannot be expressed as 156 + 4k. As a result, we've discovered the solution.

4) Find the value of [√1 ] + [√2 ] + [√3 ] + [√4 ] + ..... + [√24 ], where [x] is the greatest integer less than or equal to x.

Solution: 

Here from [ √1 ] to [ √3 ] each term has value 1, as the square root of all these numbers will be greater than equal to 1 but less than 2. The greatest integer less than those will be 1. So, the total of these three terms will be 3.

• The value of each term from [ √4 ] to [ √8 ] is 2 on the base of the same logic as explained above, so the total of these 5 terms is 10.
• From [√9 ] to [ √15], the value of each term is 3 and total of these 7 terms is 21.
• Similarly, the value of each term from [ √16 ] to [ √24 ] is 4 and the sum of these 9 terms is 36.

So, we have [√1 ] + [√2 ] + [√3 ] + [√4 ] + ..... + [√24 ] = 3 + 10 + 21 + 36 = 70.

2.7 Euler's phi-function, Euler's theorem, some properties of Euler's phi-function.

2.7.1 Euler's phi-function

The totient function , also called Euler's totient function, is defined as the number of positive integers  that are relatively prime to (i.e., do not contain any factor in common with) n, where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function , can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so 

The totient function is implemented in the Wolfram Language as EulerPhi[n].

The number , is called the cototient of n and gives the number of positive integers that have at least one prime factor in common with n.

, is always even for . By convention, , although the Wolfram Language defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command. The first few values of , for n=1, 2, ... Are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (OEIS A000010). The totient function is given by the Möbius transform of 1, 2, 3, 4, ... (Sloane and Plouffe 1995, p. 22). , is plotted above for small n.

For a prime p,

 (1)

Since all numbers less than p are relatively prime to p. If  is a power of a prime, then the numbers that have a common factor with m are the multiples of p: , , ..., . There are  of these multiples, so the number of factors relatively prime to  is

Now take a general m divisible by p. Let  be the number of positive integers not divisible by p. As before,  have common factors, so

Now let q be some other prime dividing m. The integers divisible by q are  But these duplicate  So the number of terms that must be subtracted from  to obtain  is

And

By induction, the general case is then

Where the product runs over all primes p dividing n. An interesting identity relating  to  is given by

(A. Olofsson, pers. Comm., Dec. 30, 2004).

Another identity relates the divisors  of n to n via

The totient function is connected to Möbius function  through the sum

Where the sum is over the divisors of n, which can be proven by induction on n and the fact that  and  are multiplicative (Berlekamp 1968, pp. 91-93; van Lint and Nienhuys 1991, p. 123).

The totient function has the Dirichlet generating function

For (Hardy and Wright 1979, p. 250).

The totient function satisfies the inequality

For all n except n=2 and n=6 (Kendall and Osborn 1965; Mitrinović and Sándor 1995, p. 9). Therefore, the only values of n for which  are, 4, and 6. In addition, for composite n,

 also satisfies

 (20)

Where is the Euler-Mascheroni constant. The values of  n for which  are given by 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (OEIS A100966).

The divisor function satisfies the congruence

For all primes and no composite with the exception of 4, 6, and 22, where  is the divisor function. This fact was proved by Subbarao (1974), despite the implication to the contrary, "is it true for infinitely many composite n?," stated in Guy (1994, p. 92), a query subsequently removed from Guy (2004, p. 142). No composite solution is currently known to

(Honsberger 1976, p. 35).

A corollary of the Zsigmondy theorem leads to the following congruence,

(Zsigmondy 1882, Moree 2004, Ruiz 2004ab).

The first few n for which

are given by 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (OEIS A001274), which have common values 

,2, 8, 48, 80, 96, 128, 240, 288, 480, ... (OEIS A003275).

The only for which

Is n=5186, giving

Values of  shared among n that are close together include

McCranie found an arithmetic progression of six numbers with equal totient functions,

As well as other progressions of six numbers starting at 1166400, 1749600, ... (OEIS A050518).

If the Goldbach conjecture is true, then for every positive integer m, there are primes p and q such that

(Guy 2004, p. 160). Erdős asked if this holds for p and q not necessarily prime, but this relaxed form remains unproven (Guy 2004, p. 160).

Guy (2004, p. 150) discussed solutions to

2.7.2 Properties of Euler's phi-function

To calculate the Euler totient function for any number, the following qualities are sufficient:

• For any 1qp, gcd(p,q)=11 if p is a prime number. As a result, we have:

ϕ(p)=p−1

• If p is a prime number and k1k1 is true, then there are precisely pk/p divisible by p between 1 and pk. This results in:

ϕ(pk)=pk−pk−1.

• If aa and b are substantially prime, the following is true:

ϕ(ab)=ϕ(a)⋅ϕ(b).

This relationship is not easily discernible. The Chinese remainder theorem proves it. The Chinese remainder theorem ensures that for each 0xa0xa and each 0yb, a unique 0zab with zx(moda) and zy(moda) exists (modb) It's simple to show that z is coprime to abab if and only if x and y are coprime to aa and b. As a result, the number of integers coprime to ab equals the product of a and b.

• In general, if aa and bb are not coprime, the equation is

ϕ(ab)=ϕ(a)⋅ϕ(b)⋅d

Gcd= (a,b).

As a result, we may get (n) by factorising n using the first three properties (decomposition of n into a product of its prime factors). If n=p1a1p2a2pkak, and the prime elements of n are pi, then

ϕ(n)=ϕ(p1a1)⋅ϕ(p2a2)⋯ϕ(pkak)

=(p1a1−p1a1−1)⋅(p2a2−p2a2−1)⋯(pkak−pkak−1)

=pa11⋅(1−1p1)⋅pa22⋅(1−1p2)⋯pakk⋅(1−1pk)

=n⋅(1−1p1)⋅(1−1p2)⋯(1−1pk)

2.7.3 Euler's theorem

Euler's theorem expresses the most renowned and important property of Euler's totient function:

aϕ(m)≡1(modm)

If a and m are both fairly prime

In the scenario where mm is prime, Euler's theorem is transformed into Fermat's little theorem:

Am−1≡1(modm)

Euler's theorem and Euler's totient function are both used to compute the modular multiplicative inverse, for example.

As a result, we have the following equivalence:

An≡anmodϕ(m)(modm)

This allows you to compute xnmodm for very large n, especially if n is the result of another calculation, because it allows you to compute n as a modulo.

Example:

Φ(1) = 1 

Gcd(1, 1) is 1

Φ(2) = 1

Gcd(1, 2) is 1, but gcd(2, 2) is 2.

Φ(3) = 2

Gcd(1, 3) is 1 and gcd(2, 3) is 1

Φ(4) = 2

Gcd(1, 4) is 1 and gcd(3, 4) is 1

Φ(5) = 4

Gcd(1, 5) is 1, gcd(2, 5) is 1,

Gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2

Gcd(1, 6) is 1 and gcd(5, 6) is 1,

2.8 Reduced set of residues

Modulo mm residue of aa As a result, any integer modulo m is congruent to one of the integers 0,1,2,...,m1.

A full residue system modulo mm is a collection of integers in which each integer is modulo mm congruent with exactly one other integer in the set.

The set of integers 0,1,2,...,m1 is the simplest complete residue system modulo mm. Every integer modulo mm is congruent to one of these integers.

A complete residue system modulo 5 is formed by the set of integers 0,1,2,3,4. 6,7,8,9,10 could be another full residue system modulo 55.

A reduced residue system modulo mm is a collection of integers riri such that (ri,m)=1 for all ii and rirj(mod m) for all ijij.

It's worth noting that eliminating all the components of the entire residue system set that aren't approximately prime to mm yields a reduced residue system modulo mm.

A reduced residue system modulo 6 is the set of integers 1,5.

The lemma that follows can be used to find a complete residue system modulo any positive integer m.

In mathematics, a reduced residue system modulo n is a subset R of the numbers that:

1. Gcd(r, n) = 1 for each r in R,
2. R contains φ(n) elements,
3. No two elements of R are congruent modulo n.[1][2]

The totient function of Euler is denoted by.

A reduced residue system modulo n can be created by deleting all numbers that are not relatively prime to n from a complete residue system modulo n. A full residue system modulo 12 is, for example, 0 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. The only integers in this set that are relatively prime to 12 are the so-called totatives 1, 5, 7 and 11, hence the corresponding reduced residue system modulo 12 is 1, 5, 7, 11. The totient function can be used to find the cardinality of this set: (12) = 4. Modulo 12 systems with decreased residues include:

• {13,17,19,23}
• {−11,−7,−5,−1}
• {−7,−13,13,31}
• {35,43,53,61}

If {r1, r2, ... , rφ(n)} is a reduced residue system modulo n with n > 2, then {\displaystyle \sum r_{i}\equiv 0\!\!\!\!\mod n}

{\displaystyle \sum r_{i}\equiv 0\!\!\!\!\mod n} .

A generator for the additive group of integers modulo n is every number in a reduced residue system modulo n.

Q. Find the remainder of 97! when divided by 101.

Solution

First we will apply Wilson's theorem to note that 100!≡−1(mod101). When we decompose the factorial, we get that: (100)(99)(98)(97!)≡−1(mod101)

Now we note that 100≡−1(mod101), 99≡−2(mod101), and 98≡−3(mod101). Hence:

(−1)(−2)(−3)(97!)≡−1(mod101)(−6)(97!)≡−1(mod101)(6)(97!)≡1(mod101)

Now we want to find a modular inverse of 6 (mod 101). Using the division algorithm, we get that: 101=6(16)+56=5(1)+11=6+5(−1)1=6+[101+6(−16)](−1)1=101(−1)+6(17)

Hence, 17 can be used as an inverse for 6 (mod 101). It thus follows that:

(17)(6)(97!)≡(17)1(mod101)97!≡17(mod101)

Hence, 97! has a remainder of 17 when divided by 101.

Q. Find the remainder of 67! when divided by 71.

Solution

Using Wilson's theorem, we have that 70!≡−1(mod71). Decomposing the factorial we get that:

(70)(69)(68)(67!)≡−1(mod71)(−1)(−2)(−3)(67!)≡−1(mod71)(−6)(67!)≡−1(mod71)6(67!)≡1(mod71)

Now let's find a modular inverse of 6 (mod 71) by the division algorithm:

71=6(11)+56=5(1)+11=6+5(−1)1=6+[71+6(−11)](−1)1=71(−1)+6(12)

Hence, 12 can be used as an inverse. Thus:

(12)(6)(67!)≡(12)(1)(mod71)67!≡12(mod71)

Hence when 67! is divided by 71, the remainder leftover is 12.

Q. What is the remainder of 149! when divided by 139?

Solution

From Wilson's theorem we know that 138!≡−1(mod139). We are now going to multiply both sides of the congruence until we get up to 149!:

149!≡(149)(148)(147)(146)(145)(144)(143)(142)(141)(140)(139)(−1)(mod139)149!≡(10)(9)(8)(7)(6)(5)(4)(3)(2)(1)(0)(−1)(mod139)149!≡0(mod139)

Hence the remainder of 149! when divided by 139 is 0.

In fact, this should make sense, since 149! = 149 x 148 x … x 139 x 138 x … x 2 x 1. For any primes p and q where p > q, it follows that (p−1)!≡0(modq).

Q. Simplify 146! (mod 149) to a number in the range {0, 1, . . . 148}.

Solution

Note: 149 is prime.

By Wilson’s theorem, 148! = −1 (mod 149).

x = 146! (mod 149)

147 · 148x = 147 · 148 · 146! (mod 149)

147 · 148x = 148! (mod 149)

(−2) · (−1)x = −1 (mod 149)

−2x = 1 (mod 149)

Now −2

−1 = 74 (mod 149), so

74 · −2x = 74 · 1 (mod 149)

x = 74 (mod 149)

Q. n!,ϕ(n),π(n) which denotes the number of primes less than or equal to n.

Solution

An arithmetical function is multiplicative if f(mn)=f(m)f(n) whenever gcd(m,n)=1, and totally multiplicative or completely multiplicative if this holds for any m,n. Thus f(1)=1 unless f is the zero function, and a multiplicative function is completely determined by its behaviour on the prime powers.

Q. We have seen that the Euler totient function ϕ is multiplicative but not totally multiplicative (this is one reason it is convenient to have ϕ(1)=1). The function n2 is totally multiplicative. The product of (totally) multiplicative functions is (totally) multiplicative.

Solution

Theorem: Let f(n) be a multiplicative function, and define

F(n)=∑d|nf(d).

Then F(n) is also a multiplicative function.

Proof: Let m,n be positive integers with gcd(m,n)=1. Then

F(mn)=∑d|mnf(d)=∑r|m,s|nf(rs)=∑r|m,s|nf(r)f(s)=∑r|mf(r)∑s|nf(s)=F(m)F(n)

Since r|m and s|n implies (r,s)=1.∎

We just wrote F(n) in terms of f(d). Can we do the reverse? That is, write f(n) in terms of F(d)? Yes; this is known as Möbius inversion.

Since ϕ is multiplicative, we have that

Theorem:

∑d|nϕ(n)=n

This theorem can also be proved using basic facts about cyclic groups.

Q. The divisors of 12 are 1,2,3,4,6,12. Their totients are 1,1,2,2,2,4 which sum to 12.

Solution

The function f(n)=1 is (totally) multiplicative. Let d(n) be the number of divisors of n. Then since d(n)=∑d|n1 we see that d(n) is multiplicative.

The function f(n)=n is (totally) multiplicative. Let σ(n) be the sum of divisors of n. Then since σ(n)=∑d|n we see that σ(n) is multiplicative. In general, we can apply this trick to any power of n.

Q. The number 2 1000 is divided by 13. What is the remainder?

Solution

We know that 2

12 ≡ 1 (mod 13). So we first take out as many factors of 2 12 as possible. We can write 1000 as 83 · 12 + 4 (which is another way of saying that 1000 ≡ 4 (mod 12). So 2

1000 = 212·83+4 = (212)83· 2

4 ≡ 2

4 = 16 ≡ 3 (mod 13).

Q. Find the value of [√1 ] + [√2 ] + [√3 ] + [√4 ] + ..... + [√24 ], where [x] is the greatest integer less than or equal to x.

Solution: 

Here from [ √1 ] to [ √3 ] each term has value 1, as the square root of all these numbers will be greater than equal to 1 but less than 2. The greatest integer less than those will be 1. So, the total of these three terms will be 3.

• The value of each term from [ √4 ] to [ √8 ] is 2 on the base of the same logic as explained above, so the total of these 5 terms is 10.
• From [√9 ] to [ √15], the value of each term is 3 and total of these 7 terms is 21.
• Similarly, the value of each term from [ √16 ] to [ √24 ] is 4 and the sum of these 9 terms is 36.

So, we have [√1 ] + [√2 ] + [√3 ] + [√4 ] + ..... + [√24 ] = 3 + 10 + 21 + 36 = 70.

References:

1. Thomas Koshy, Elementary Number Theory with Applications (2nd Edition), Academic Press, 2007.

2. Neville Robinns, Beginning Number Theory (2ndEdition), Narosa Publishing House Pvt. Limited, Delhi,2007.