1

I have a homework to hand in and they asked this question. I don't know if I'm supposed to count 1 as a prime to that number or not.

In my case $p=3947$, so I count 3945 numbers fitting that criteria since $p$ is prime.

Is this correct ?

Thanks.

BrainOverfl0w
  • 197
  • 8
  • 1
    I would definitely count 1, since the normal definition if "prime to ..." is that the greatest common factor should be 1. – Old John Nov 15 '12 at 15:16
  • 2
    There are not 3945 primes lower than $3947$. – Arthur Nov 15 '12 at 15:21
  • 1
    I understand that he is not counting primes below $p$, but rather numbers below $p$ which are "prime to $p$", i.e. relatively prime to $p$. – Old John Nov 15 '12 at 15:30
  • It seems likely that your homework question is asking "How many numbers exist that are smaller than $p$ and prime with $p$?" In this case, you should definitely count 1. But you ask "How many prime numbers...?", which is a very different question. A number can be prime with 3947 without actually being a prime number. For the sake of getting the right answer, be sure you understand the difference between these two questions and figure out which question your homework is asking. – Jonas Kibelbek Nov 15 '12 at 15:32
  • 1
    @JonasKibelbek : I edited the question to be clearer. You're right that it's a different question. – BrainOverfl0w Nov 15 '12 at 15:35
  • 2
    $p=3947$ is prime. Therefore the answer is $\phi(p)=p-1=3946$. – PAD Nov 15 '12 at 15:52

1 Answers1

1

The correct terminology is 'co-prime' with p. And there's a known formula for it. Euler's totient. look at http://en.wikipedia.org/wiki/Euler_totient_function.

mousomer
  • 395
  • 2
  • 7