Find all positive integers......

[Poirot1]

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]

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$

 

[Nono713]

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

 

[Poirot1]

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

 

[Nono713]

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.

 

[Poirot1]

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}$

 

[Nono713]

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? :)

 

[Poirot1]

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.