Cheenta

Academy for Gifted Students

How Cheenta works to ensure student success?

Explore the Back-StoryLet $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$

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

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$

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$

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$

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

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$

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$

Cheenta is a knowledge partner of Aditya Birla Education Academy

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIALAcademic Programs

Free Resources

Why Cheenta?

Online Live Classroom Programs

Online Self Paced Programs [*New]

Past Papers

More