Skip to main content
edited body
Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

Let $p$ isbe a prime such that $p \equiv 7 \bmod 8$, then $2$ is a quadratic residue mod $p$ and $\frac{p-1}{2}$ is odd.

Hence, if we take $k= \prod_{p \le x, p \equiv 7 \bmod 8} \frac{p-1}{2}$, then $n$ is divisible by all $p \le x$ of the form $p \equiv 7 \bmod 8$, and $k$ is odd. We get $$\frac{\phi(n)}{n} = \prod_{p \mid n} (1-\frac{1}{p}) \le \prod_{p \le x, p \equiv 7 \bmod 8} (1-\frac{1}{p}) \le e^{-\sum_{p \le x, p \equiv 7 \bmod 8} \frac{1}{p}},$$ which goes to 0 as $x \to \infty$, by Dirichlet's theorem on primes in arithmetic progressions. Hence, the answer is 'no'.

Let $p$ is a prime such that $p \equiv 7 \bmod 8$, then $2$ is a quadratic residue mod $p$ and $\frac{p-1}{2}$ is odd.

Hence, if we take $k= \prod_{p \le x, p \equiv 7 \bmod 8} \frac{p-1}{2}$, then $n$ is divisible by all $p \le x$ of the form $p \equiv 7 \bmod 8$, and $k$ is odd. We get $$\frac{\phi(n)}{n} = \prod_{p \mid n} (1-\frac{1}{p}) \le \prod_{p \le x, p \equiv 7 \bmod 8} (1-\frac{1}{p}) \le e^{-\sum_{p \le x, p \equiv 7 \bmod 8} \frac{1}{p}},$$ which goes to 0 as $x \to \infty$, by Dirichlet's theorem on primes in arithmetic progressions. Hence, the answer is 'no'.

Let $p$ be a prime such that $p \equiv 7 \bmod 8$, then $2$ is a quadratic residue mod $p$ and $\frac{p-1}{2}$ is odd.

Hence, if we take $k= \prod_{p \le x, p \equiv 7 \bmod 8} \frac{p-1}{2}$, then $n$ is divisible by all $p \le x$ of the form $p \equiv 7 \bmod 8$, and $k$ is odd. We get $$\frac{\phi(n)}{n} = \prod_{p \mid n} (1-\frac{1}{p}) \le \prod_{p \le x, p \equiv 7 \bmod 8} (1-\frac{1}{p}) \le e^{-\sum_{p \le x, p \equiv 7 \bmod 8} \frac{1}{p}},$$ which goes to 0 as $x \to \infty$, by Dirichlet's theorem on primes in arithmetic progressions. Hence, the answer is 'no'.

Source Link
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

Let $p$ is a prime such that $p \equiv 7 \bmod 8$, then $2$ is a quadratic residue mod $p$ and $\frac{p-1}{2}$ is odd.

Hence, if we take $k= \prod_{p \le x, p \equiv 7 \bmod 8} \frac{p-1}{2}$, then $n$ is divisible by all $p \le x$ of the form $p \equiv 7 \bmod 8$, and $k$ is odd. We get $$\frac{\phi(n)}{n} = \prod_{p \mid n} (1-\frac{1}{p}) \le \prod_{p \le x, p \equiv 7 \bmod 8} (1-\frac{1}{p}) \le e^{-\sum_{p \le x, p \equiv 7 \bmod 8} \frac{1}{p}},$$ which goes to 0 as $x \to \infty$, by Dirichlet's theorem on primes in arithmetic progressions. Hence, the answer is 'no'.