Divisibility In Z & Euler Function MCQ Quiz - Objective Question with Answer for Divisibility In Z & Euler Function - Download Free PDF

Concept:

Number of Divisors of a Number:

• To find the total number of positive divisors of a number, we first perform its prime factorization.
• If a number is expressed as a product of prime powers: a = p^c₁ × q^c₂ × r^c₃..., then the number of positive divisors is:
• Number of divisors = (c₁ + 1)(c₂ + 1)(c₃ + 1)...
• This includes both 1 and the number itself as divisors.

Calculation:

Given number = 1080

⇒ 1080 ÷ 2 = 540

⇒ 540 ÷ 2 = 270

⇒ 270 ÷ 2 = 135

⇒ 135 ÷ 3 = 45

⇒ 45 ÷ 3 = 15

⇒ 15 ÷ 3 = 5

⇒ 5 ÷ 5 = 1

⇒ Prime factorization of 1080 = 2³ × 3³ × 5

Now, using the formula:

⇒ Number of divisors = (3 + 1)(3 + 1)(1 + 1)

⇒ Number of divisors = 4 × 4 × 2

∴ Hence, the number of positive divisors of 1080 is 32.

Concept:

As a + b ≡ 0 (mod a + b) so, \(a^{2m-1}+b^{2m-1}≡ 0\) (mod a+b) where m is any positive integer

Explanation:

139 + 239 + 339 + ... + 9839

Here 1 + 98 ≡ 0 (mod 99), 2 + 97 ≡ 0 (mod 99), 3 + 96 ≡ 0 (mod 99), ....49 + 50 ≡ 0 (mod 99)

So, 1³⁹+ 98³⁹ ≡ 0 (mod 99), 239+ 9739 ≡ 0 (mod 99), 339+ 9639 ≡ 0 (mod 99), ...., 4939+ 5039 ≡ 0 (mod 9)

Adding them we get

139 + 239 + 339 + ... + 9839  ≡ 0 (mod 99)

Hence 139 + 239 + 339 + ... + 9839  is equal to 0 in ℤ/99ℤ

(3) is correct

Concept Used:

For a positive integer n, Euler's totient function is defined as follows:

\( \phi(n) = \text{number of positive integers } k \leq n \text{ such that } \text{gcd}(n, k) = 1\)

Here, gcd(n, k) represents the greatest common divisor of n and k.

Some properties of Euler's totient function include:

• ϕ(1)  = 1, as 1 has no positive integers less than itself.
• If p is a prime number, then ϕ(p)  = p - 1, as all positive integers less than p are relatively prime to p.
• For any two distinct prime numbers p and q, ϕ(pq) = (p - 1)(q - 1), due to the property that the totient function is multiplicative for relatively prime numbers.
• ϕ(n) is even for n ≥ 3, except for powers of 2, where ϕ(2^k) = 2^k-1.

Explanation:

Using the properties, we can calculate the values as follows:

ϕ(10) = ϕ(2 × 5) = (2 -1)(5 - 1) = 1 × 4 = 4

ϕ(15) = ϕ(3 × 5) = (3 - 1)(5 - 1) = 2 × 4 = 8

ϕ(12) = ϕ(2² × 3) = (2^2-1)(3 - 1) = 2 × 2 = 4

For n = 25,

The positive integers less than or equal to 25 are 1, 2, 3, ..., 25.

Numbers relatively prime to 25 are 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24.

So, ϕ(25)=20.

Thus, option 1 and option 4 are correct.

Concept:

d(n) = number of positive divisors of n

v(n) = number of distinct prime divisors of n

ω(n) = number of prime divisors of n counted with multiplicity 

 n = p1r1p2r2........pkrk 

then d(n) = (r1+1)(r2+1)........(rk+k)

ω (n) = r1+ r2+........+ rk

v(n) = k 

Explanation:

(1) n = (37)² 

Then ω(n) = 2 

d(n) = 3

and log n = log (37)² = 2log (37) > 3

Therefore, option (1) is not correct.

(2) n = p₁^r₁p₂^r₂........p_k^r_k 

d(n) = (r₁+1)(r₂+1)........(r_k+k)

3√ n = 3^{\(p_1^{\frac{r_1}{2}}p_2^{\frac{r_2}{2}}........p_k^{\frac{r_k}{2}}\)}

Clearly d(n) ≤ 3√ n ∀ n ∈ N

Therefore, there does not exist n ∈ N ; d(n) > 3√ n

Therefore, Option (2) is not true. 

(3) Let n = p1r1p2r2........pkrk 

d(n) = (r1+1)(r2+1)........(rk+k)

v(n) = k 

ω (n) = r₁+ r₂+........+ r_k

2^v(n) = 2^k, 2^{ω (n)}= 2^{r₁+r₂+.....+r_k}

⇒2^v(n) ≤ d(n) ≤ 2r1+r2+.....+rk

⇒2v(n)  ≤ d(n) ≤ 2^ω(n) 

Therefore, option (3) is correct.

(4) n = 9 = 3²

m = 3x7 = 21

ω(n) = ω(m) = 2 

d(n) = 3

d(m) = 4

Therefore, d(n) ≠ d(m)

Therefore, option (4) is not correct.

Concept:

a ≡ b mod m means m divides a - b.

Explanation:

n ≡ 1 mod 7

Then 7/(n - 1)

n - 1 = 7k, k ∈ \(\mathbb Z\) 

n ≡ 4 mod 15 

n - 4 = 15k₁, k1 ∈ \(\mathbb Z\)

Then n = 64

64 - 1 = 63 divisible by 3

So, n is congruent to 1 mad 3.  

(1) is correct

64 - 1 = 63 not divisible by 35

So, n is not congruent to 1 mad 35.  

(2) is false

64 - 1 = 63 not divisible by 21

n is congruent to 1 mod 21.  

(3) is correct

64 - 1 = 63 not divisible by 5

n is not congruent to 1 mod 5.  

(4) is false

Explanation:

For this type of problems, just try to discard given options by taking suitable counter examples..

For option (1). Let n = 16 then

(n - 1)! + 3 = 15! + 3 = even + odd = odd

⇒ No any even integer divide it ie to (n - 1)! + 3

⇒ option (1) is false. (Because z not true for all)

For option (2). taken n = 17, then

∵ (n - 1)! = 16! , Here n = 17 is prime so it will never divide 16!

⇒ option (2) false.

For option (4). take n = 16, then n² = 16² + n! + 1 = 16 ! + 1 Here 16² is even while 16! + 1 is odd integer So 16² + 16! + 1 

⇒ option (4) is false.

For option (3) is true [consider any n ≥ 16 even]

Note: Proof for this option is too long, so just pay to understand with example.

\(=\frac{p_1^{r_1} p_2^{r_2} \cdots p_n^{r_n}}{p_1^{r_1-1} \cdot\left(p_1-1\right) \cdot p_2^{r_2-1}\left(p_2-1\right) \ldots p_n^{r_{n-1}}\left(p_{n-1}\right)}\)

\(=\frac{p_1 p_2 \cdots p_n}{\left(p_1-1\right)\left(p_2-1\right) \cdots\left(p_n-1\right)}\) = integer (given) = p/n¹/n

∵ (p₁ - 1) × p₁ ⇒ ∃ some other prime p₂ S.t (p₁ - 1)|p₂

But ∵  p₂ is also a prime, so not divisible by any of integer except 1 .

(there of one prime factor. is 2, then n tar as at most two distinct prime faster else one.

thus, option (3) is true

Concept:

A mapping ϕ: \(\mathbb N\) →  \(\mathbb N\) defined by ϕ(n) = {x ∈ \(\mathbb N\) | 1 ≤ x

ϕ (pⁿ) = pⁿ - p^n-1

ϕ(mn) = ϕ(m)ϕ(n) if gcd(m, n) = 1 
Explanation:

ϕ(n) table:

From the table of ϕ(n) we can see that if we take n as a prime number greater than 3, then ϕ(n) > ϕ(n+1) and if we take n + 1 as a prime number greater than 3, then ϕ(n) < ϕ(n+1)  

∴ options (1) and (2) are correct.

ϕ(n) table:

So if we take N = 6, then ∀ n > 6, we have ϕ(N) < ϕ(n)

So option (3) is correct 

So the option that is not true is (4)

Explanation:

Given 1 ≤ n ≤ 999

Number of integers n such that 1 ≤ n ≤ 999 and divisible by 3 is\(\left[\frac{999}{3}\right]\) = 333

Number of integers n such that 1 ≤ n ≤ 999 divisible by 37 is

\(\left[\frac{999}{37}\right]\) = 27

LCM of 3 and 37 = 3 × 37 = 111

So Number of integers n such that 1 ≤ n ≤ 999 divisible by both 3 and 37 is \(\left[\frac{999}{111}\right]\) = 9

So integers contains in S = 333 + 27 - 9 - 351

Therefore integers contains in S^c = 999 - 351 = 648

∴ The number of integers in the set S^c is 648.

Concept:

A cyclic group of order 'n' has ϕ(n) generators.    

 For  n = \(p_1^{a_1}⋅ p_2^{a_2}⋅ p_3^{a_3}.....p_k^{a_k}\)     

where, p1, p2, ......, pk  are distinct primes, then   

ϕ(n) =  \(ϕ(p_1^{a_1})⋅ ϕ(p_2^{a_2})⋅ ϕ(p_3^{a_3}).....ϕ(p_k^{a_k})\)

Also \(ϕ(p^a) = p^a -p^{a-1}\)

Explanation:

Therefore, 

ϕ(36) = ϕ(6² ) = ϕ (2² ⋅ 3²) = ϕ (2²) ⋅ ϕ(3²) = (2² - 2) (3² - 3)

= (2) (6) = 12   

Hence 12 generators will be there 

(2) is correct                    

Concept:

As a + b ≡ 0 (mod a + b) so, \(a^{2m-1}+b^{2m-1}≡ 0\) (mod a+b) where m is any positive integer

Explanation:

 137 + 237 + 337 + ... + 8837 

Here 1 + 88 ≡ 0 (mod 89), 2 + 87 ≡ 0 (mod 89), 3 + 86 ≡ 0 (mod 89), ....44 + 45 ≡ 0 (mod 89)

So, 1³⁷+ 88³⁷ ≡ 0 (mod 89), 237+ 8737 ≡ 0 (mod 89), 337+ 8637 ≡ 0 (mod 89), ...., 4437+ 4537 ≡ 0 (mod 89)

Adding them we get

137 + 237 + 337 + ... + 8837 ≡ 0 (mod 89)

Hence 137 + 237 + 337 + ... + 8837 is equal to 0 in ℤ/89ℤ

(4) is correct

Concept:

Fermat's last theorem: Let n ∈ \(\mathbb{N}\) and n ≥ 3 then there does not exist x, y, z ∈ \(\mathbb{N}\) such that xn + yn = zn   

Explanation:

F(n) = |A_n| and An = {(x, y, z) ∈ \(\mathbb{N}\)3∶  xn + yn = zn  and  z < n}.

For  n = 1

A1 = {(x, y, z) ∈ \(\mathbb{N}\)3∶  x1 + y1 = z1  and  z < 1}.

Now since z ∈ \(\mathbb{N}\) so z can't be < 1.

Hence A1 = {ϕ}

so F(1) = 0

For n = 2

A2 = {(x, y, z) ∈ \(\mathbb{N}\)3∶  x2 + y2 = z2  and  z < 2}.

Now since z ∈ \(\mathbb{N}\) and z < 2 so z = 1

 x2 + y2 = 1

Now, x, y ∈ \(\mathbb{N}\) so x ≥ 1, y ≥ 1

hence  x2 + y2 ≥ 1 + 1 = 2

So there is not such x, y exist such that x2 + y2 = 1

Hence A2 = {ϕ}

so F(2) = 0

Now from Fermat's last theorem, 

An = {ϕ} for all n ≥ 3

so F(n) = 0 for all n ≥ 3

Hence F(n) is always finite for n ≥ 3 and F(n) = 0 for all n 

option (1) and (3) are correct

Explanation:

Recall Euler's theorem

if n is any positive integer & GCD (a,n) = 1

then aϕ (n) ≡ 1 (mod n) .....(i)

Here, for last two digit we have to calculate 

32019 mod 100

so, from (i) 

3ϕ(100) ≡ 1 mod (100)

∵ ϕ (100) = 40 & 2019 = 40 × 50 + 19

So, 32019 ≡ (340)50 . 319 mod (100)

≡ 319 mod (100)

≡ 67 ...opt(d) TRUE

319 ≡ 36.36​.36​.3 = mod(100)

≡ 67 (mod 100)

(In Z100

31 ≡ 3, 32 ≡ 9, 33 ≡ 27, 34 ≡ 81, 35 ≡ 43, 36 ≡ 29,.....)

Option (4) is correct

Explanation:

For this type of problems, just try to discard given options by taking suitable counter examples..

For option (1). Let n = 16 then

(n - 1)! + 3 = 15! + 3 = even + odd = odd

⇒ No any even integer divide it ie to (n - 1)! + 3

⇒ option (1) is false. (Because z not true for all)

For option (2). taken n = 17, then

∵ (n - 1)! = 16! , Here n = 17 is prime so it will never divide 16!

⇒ option (2) false.

For option (4). take n = 16, then n² = 16² + n! + 1 = 16 ! + 1 Here 16² is even while 16! + 1 is odd integer So 16² + 16! + 1 

⇒ option (4) is false.

For option (3) is true [consider any n ≥ 16 even]

Note: Proof for this option is too long, so just pay to understand with example.

\(=\frac{p_1^{r_1} p_2^{r_2} \cdots p_n^{r_n}}{p_1^{r_1-1} \cdot\left(p_1-1\right) \cdot p_2^{r_2-1}\left(p_2-1\right) \ldots p_n^{r_{n-1}}\left(p_{n-1}\right)}\)

\(=\frac{p_1 p_2 \cdots p_n}{\left(p_1-1\right)\left(p_2-1\right) \cdots\left(p_n-1\right)}\) = integer (given) = p/n¹/n

∵ (p₁ - 1) × p₁ ⇒ ∃ some other prime p₂ S.t (p₁ - 1)|p₂

But ∵  p₂ is also a prime, so not divisible by any of integer except 1 .

(there of one prime factor. is 2, then n tar as at most two distinct prime faster else one.

thus, option (3) is true

Concept:

As a + b ≡ 0 (mod a + b) so, \(a^{2m-1}+b^{2m-1}≡ 0\) (mod a+b) where m is any positive integer

Explanation:

139 + 239 + 339 + ... + 9839

Here 1 + 98 ≡ 0 (mod 99), 2 + 97 ≡ 0 (mod 99), 3 + 96 ≡ 0 (mod 99), ....49 + 50 ≡ 0 (mod 99)

So, 1³⁹+ 98³⁹ ≡ 0 (mod 99), 239+ 9739 ≡ 0 (mod 99), 339+ 9639 ≡ 0 (mod 99), ...., 4939+ 5039 ≡ 0 (mod 9)

Adding them we get

139 + 239 + 339 + ... + 9839  ≡ 0 (mod 99)

Hence 139 + 239 + 339 + ... + 9839  is equal to 0 in ℤ/99ℤ

(3) is correct

Concept:

d(n) = number of positive divisors of n

v(n) = number of distinct prime divisors of n

ω(n) = number of prime divisors of n counted with multiplicity 

 n = p1r1p2r2........pkrk 

then d(n) = (r1+1)(r2+1)........(rk+k)

ω (n) = r1+ r2+........+ rk

v(n) = k 

Explanation:

(1) n = (37)² 

Then ω(n) = 2 

d(n) = 3

and log n = log (37)² = 2log (37) > 3

Therefore, option (1) is not correct.

(2) n = p₁^r₁p₂^r₂........p_k^r_k 

d(n) = (r₁+1)(r₂+1)........(r_k+k)

3√ n = 3^{\(p_1^{\frac{r_1}{2}}p_2^{\frac{r_2}{2}}........p_k^{\frac{r_k}{2}}\)}

Clearly d(n) ≤ 3√ n ∀ n ∈ N

Therefore, there does not exist n ∈ N ; d(n) > 3√ n

Therefore, Option (2) is not true. 

(3) Let n = p1r1p2r2........pkrk 

d(n) = (r1+1)(r2+1)........(rk+k)

v(n) = k 

ω (n) = r₁+ r₂+........+ r_k

2^v(n) = 2^k, 2^{ω (n)}= 2^{r₁+r₂+.....+r_k}

⇒2^v(n) ≤ d(n) ≤ 2r1+r2+.....+rk

⇒2v(n)  ≤ d(n) ≤ 2^ω(n) 

Therefore, option (3) is correct.

(4) n = 9 = 3²

m = 3x7 = 21

ω(n) = ω(m) = 2 

d(n) = 3

d(m) = 4

Therefore, d(n) ≠ d(m)

Therefore, option (4) is not correct.