Welcome to our community

Be a part of something great, join today!

Number Theory Find all positive integers.....

  • Thread starter
  • Banned
  • #1

Poirot

Banned
Feb 15, 2012
250
Find all positive integers n such that $\phi(n)=6$.
n>1 so we can write n as a product of primes, say $p_{1},....,p_{t}$ are the prime factors.
Then, using the multiplicative property, we find that

$n(1-p_{1})....(1-p_{t})=6p_{1}....p_{t}$. I've tried using odd/even arguments to deduce information about the primes but I have been unsuccessful.
 

chisigma

Well-known member
Feb 13, 2012
1,704
Find all positive integers n such that $\phi(n)=6$.
n>1 so we can write n as a product of primes, say $p_{1},....,p_{t}$ are the prime factors.
Then, using the multiplicative property, we find that

$n(1-p_{1})....(1-p_{t})=6p_{1}....p_{t}$. I've tried using odd/even arguments to deduce information about the primes but I have been unsuccessful.
The fact that $6 + 1 = 7$ and $7$ is prime means that $7$ and $2 \cdot 7 = 14$ both satisfy the condition. The other numbers satisfying the condition are $9$ and $18$ and that is easily found from the definition of $\varphi(n)$...

Kind regards

$\chi$ $\sigma$
 
Last edited:

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
Because $6$ is a multiple of $2$ but not of $4$, an $n$ such that $\varphi{(n)} = 6$ must be such that, for odd prime $p$:

$$n = 2^r \cdot p^k ~ ~ \text{with} ~ ~ r + k \leq 2$$
Since $2$ can divide $\varphi{(n)}$ only once. Hence by observation the solutions are:

$$r = 0, ~ k = 0 ~ ~ \implies ~ ~ \text{no solutions}$$
$$r = 0, ~ k = 1 ~ ~ \implies ~ ~ n = 7$$
$$r = 0, ~ k = 2 ~ ~ \implies ~ ~ n = 3^2 = 9$$
$$r = 1, ~ k = 0 ~ ~ \implies ~ ~ n = 2 \cdot 7 = 14$$
$$r = 1, ~ k = 1 ~ ~ \implies ~ ~ n = 2 \cdot 3^2 = 18$$
$$r = 2, ~ k = 0 ~ ~ \implies ~ ~ \text{no solutions}$$

(if $n$ was a product of two or more distinct odd primes, then its totient would be divisible by 4)

Yeah, this reasoning is kind of flaky but it works :p
 
Last edited:
  • Thread starter
  • Banned
  • #4

Poirot

Banned
Feb 15, 2012
250
Because $6$ is a multiple of $2$ but not of $4$, an $n$ such that $\varphi{(n)} = 6$ must be such that, for odd prime $p$:
How do you know 2 divides n? Am I missing some theorem that relates the divisors of
phi(n) to the divisors of n?

Also, how do you r+k<_2?

Thanks
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
How do you know 2 divides n? Am I missing some theorem that relates the divisors of
phi(n) to the divisors of n?

Also, how do you r+k<_2?
If an odd prime $p$ divides $n$, then $p - 1$ divides $\varphi{(n)}$, and $p - 1$ is then even.

Write $n = 2^r p^k$ so $\varphi{(n)} = 2^{r - 1} (p - 1) p^{k - 1}$, what is the condition for $2 \mid \varphi{(n)}$ and $4 \nmid \varphi{(n)}$?

We see we must have $(r - 1) < 1$, so $r < 2$.

Try plugging in $r = 0$, $r = 1$, and see what you get for $n$. Then show that if $r > 1$, there can be no solutions (hint: in this case we see that $2$ divides $\varphi{(n)}$ from the power of two, but $2$ divides $\varphi{(n)}$ again from $p - 1$, so $4$ divides $\varphi{(n)}$, which is impossible since $\varphi{(n)} = 6$).

You are right I made a mistake, the value of $k$ doesn't matter, so I put too many conditions. Fortunately no solution was lost by my blunder.
 
Last edited:
  • Thread starter
  • Banned
  • #6

Poirot

Banned
Feb 15, 2012
250
If an odd prime $p$ divides $n$, then $p - 1$ divides $\varphi{(n)}$, and $p - 1$ is then even.

.
I am still confused as how you can wrie $n=2^{r}p^{k}$
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
I am still confused as how you can wrie $n=2^{r}p^{k}$
We are looking at how many times $2$ divides $\varphi{(n)}$. Now, what if $n$ was divisible by two distinct odd primes? Then, for some $a$:

$$n = a \cdot p \cdot q$$
So:

$$\varphi{(n)} = \varphi{(a)} \cdot (p - 1) \cdot (q - 1)$$
But now $p - 1$ and $q - 1$ are both even, so $\varphi{(n)}$ is a multiple of four! Impossible, since $\varphi{(n)} = 6$.

So now we know that $n$ can consist of at most one odd prime! Now, we also know that it must consist of at least one odd prime, since it cannot be a power of two (since $\varphi{(n)}$ is not a power of two). Therefore, $n$ has as a factor exactly one odd prime. Finally, we consider even primes, namely $2$, and so we can let:

$$n = 2^r \cdot p^k$$

That is, the product of one even prime (the only even prime) to some power, and of some odd prime power. And the analysis in the previous post follows..

Does it make more sense to you now? :)
 
Last edited:
  • Thread starter
  • Banned
  • #8

Poirot

Banned
Feb 15, 2012
250
We are looking at how many times $2$ divides $\varphi{(n)}$. Now, what if $n$ was divisible by two distinct odd primes? Then, for some $a$:

$$n = a \cdot p \cdot q$$
So:

$$\varphi{(n)} = \varphi{(a)} \cdot (p - 1) \cdot (q - 1)$$
But now $p - 1$ and $q - 1$ are both even, so $\varphi{(n)}$ is a multiple of four! Impossible, since $\varphi{(n)} = 6$.

So now we know that $n$ can consist of at most one odd prime! Now, we also know that it must consist of at least one odd prime, since it cannot be a power of two (since $\varphi{(n)}$ is not a power of two). Therefore, $n$ has as a factor exactly one odd prime. Finally, we consider even primes, namely $2$, and so we can let:

$$n = 2^r \cdot p^k$$

That is, the product of one even prime (the only even prime) to some power, and of some odd prime power. And the analysis in the previous post follows..

Does it make more sense to you now? :)
Yes, thanks mate.