How Cheenta works to ensure student success?
Explore the Back-Story

# ISI B.Math objective 2006 problem -2 Number theory (Euler phi function)

## PROBLEM

Let $p$ be an odd prime.Then the number of positive integers less than $2p$ and relatively prime to $2p$ is:

(A)$p-2$ (B) $\frac{p+1}{2}$(C) $p-1$(D)$p+1$

## SOLUTION

This is a number theoretic problem .We can solve this problem in 2 different methods. Let us see them both one by one

## Method -1

Let us look at the prime factorization of $2p$ it is

$2p=2\cdot p$

Note that there are $2p-1$ numbers that are less than $2p$

$2p$ is an even number so it has a common divisor with each of the even numbers that are smaller than $2p$ i.e. the numbers in the following set

${2,4,6,\dots(2p-2)}$

So we can disregard these $(p-1)$ numbers

Next note that $p$ is an odd prime number so the only odd number smaller than $2p$ that can have a common divisor with $2p$ is $p$ so we have to disregard this number too

Taking all these into account we come to conclusion that the no of positive integers less than $2p$ and relatively prime to $2p$ is $(2p-1)-(p-1)-1=p-1$

## Method-2

We can also use Euler totient function or phi function to solve this problem

We know that Euler phi function is multiplicative i.e $\phi(m\cdot n)=\phi(m)\cdot \phi(n)$ for any positive integers $m$ and $n$

So We can write $\phi(2 \cdot p)=\phi(2)\phi(p)$

Now $\phi(p)$ is the no of positive integers that are less than $p$ and are relatively prime to to $p$ .

As $p$ is a prime no ,so this number is equal to $p-1$

similarly $\phi(2)=1$

As $\phi$ is multiplicative so we get $\phi(2p)=1\cdot(p-1)=p-1$

## PROBLEM

Let $p$ be an odd prime.Then the number of positive integers less than $2p$ and relatively prime to $2p$ is:

(A)$p-2$ (B) $\frac{p+1}{2}$(C) $p-1$(D)$p+1$

## SOLUTION

This is a number theoretic problem .We can solve this problem in 2 different methods. Let us see them both one by one

## Method -1

Let us look at the prime factorization of $2p$ it is

$2p=2\cdot p$

Note that there are $2p-1$ numbers that are less than $2p$

$2p$ is an even number so it has a common divisor with each of the even numbers that are smaller than $2p$ i.e. the numbers in the following set

${2,4,6,\dots(2p-2)}$

So we can disregard these $(p-1)$ numbers

Next note that $p$ is an odd prime number so the only odd number smaller than $2p$ that can have a common divisor with $2p$ is $p$ so we have to disregard this number too

Taking all these into account we come to conclusion that the no of positive integers less than $2p$ and relatively prime to $2p$ is $(2p-1)-(p-1)-1=p-1$

## Method-2

We can also use Euler totient function or phi function to solve this problem

We know that Euler phi function is multiplicative i.e $\phi(m\cdot n)=\phi(m)\cdot \phi(n)$ for any positive integers $m$ and $n$

So We can write $\phi(2 \cdot p)=\phi(2)\phi(p)$

Now $\phi(p)$ is the no of positive integers that are less than $p$ and are relatively prime to to $p$ .

As $p$ is a prime no ,so this number is equal to $p-1$

similarly $\phi(2)=1$

As $\phi$ is multiplicative so we get $\phi(2p)=1\cdot(p-1)=p-1$

This site uses Akismet to reduce spam. Learn how your comment data is processed.