Question

How many positive integers n less than 1000, have the property that the number of positive integers less than n which are coprime to n, is exactly n/3?

Answer 1

Your asking for the number of solutions to $$\phi(n)=\frac{n}{3}$$ for $$1\leq n\leq 1000$$ Where phi is eulers totient function

Answer 2

Sense, $$\phi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$$

Answer 3

Your asking for the integers n between 1 and 1000, with $$\prod_{p\mid n}(1-\frac{1}{p})=\frac{1}{3}$$

Answer 4

I was attempting to answer this, but I got myself confused just trying to get my head around what the question wanted you to do...
I think you're in good hands with @Jack174 :)

Answer 5

@thongkun Honestly, I don't see a really good way to do this. I would just recommend a brute force search, you can implement eulers totient function applied to n in mathematica as EulerPhi[n]

Answer 6

it's hard for me. Please bring out the simple solution.

Answer 7

Do you just want the answer

Answer 8

Its 25.

Answer 9

not just the answer

Answer 10

As in No, I just want ther answer or, No I don't just want the answer?

Answer 11

As I said it is 25.

Answer 12

Can I ask where you found this problem?

Answer 13

I found it on ''Brilliant.org'' .

Answer 14

why are you doing that, do you enjoy solving arbitrary problems

Answer 15

I am studying euler totient. I want to know how you can come the answe up

Answer 16

http://www.wolframalpha.com/input/?i=Eulerphi%5Bn%5D%3Dn%2F3%2C+n%5Cleq1000

Answer 17

I don't understand why you are doing this, if your interested in mathematics I would have thought your time would be better spent just studying.

Answer 18

?

Answer 19

why are you solving problems there

Answer 20

@thongkun Do you understand what the Euler Totient Function is actually used for?

Answer 21

I am now studying to understand @sarahusher

Answer 22

Thanks @Jack174 :)

Answer 23

Okay, so the first thing to understand is what the totient function is used for.

It's used to find out "of all the integers less than a number 'n', how many of those integers are coprime to n'

so for example
\[\Phi(98)=\Phi(2 \times 7^{2})\]
using the formula for Euler's Totient Function, we find that there are 42 different numbers which are less than 98, that are coprime to 98.

Does that help at all?
I'm sorry I can't help you with your original question but I can maybe help you understand what it is used for :)

Answer 24

u have \[\prod_{p_k\mid n}(1-\frac{1}{p_k})=\frac{1}{3}\]hint: \(p_k \in\text{{2,3}}\)

Answer 25

There could be some other finite set of distinct primes whose resulting product is equal to a third.

Answer 26

ok, u have\[3\prod (p_k-1)=\prod p_k\]now\[3|\prod p_k\]so one of them must be 3

and \(\prod (p_k-1) | \prod p_k\) only possible prime is 2

Answer 27

so \(n\) must be in the form \[n=2^{\alpha}3^{\beta}\]where \(\alpha\) and \(\beta\) are positive integers

Answer 28

Your first line make sense, not following your last line.

Answer 29

$$\prod_{p\in \text{S} }p-1\mid \prod_{p\in \text{S}}p\implies \text{S={2}}$$

Answer 30

I don't folllow.

Answer 31

lets look at it in other way\[\prod \frac{p_k}{p_k-1}=3\]can \(p_k\) take a prime greater than 3? id probably say no because if \(p_k>3\) LHS will be divisible by that prime and RHS not.

Answer 32

right :)

Answer 33

I don't understand what your saying

Answer 34

though

Answer 35

I now see why its true, making an argument that p-1 is divisible by two and the numerator wont be divisible by enough powers of 2 because its a product of primes, in general if his problem was for the number of integers less then or equal to x that satisfy this constraint, it would be $$\sum_{k=1}^{[\log_2[x]]}[\log_3[\frac{x}{2^k}]]$$ Where the braces denote the floor function.

Answer 36

Is the number opositive integers n less than x, have the property that the number of positive integers less than n which are coprime to n, is exactly n/3?

Answer 37

Substituting x=1000, gives the solution 24 as required, nice solution muk

Answer 38

Thanks and that closed form is interesting :)