Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Based on my understanding, the totient of any number K is the number of relative primes to K, i.e. numbers less than or equal to K that do not share a divisor.

Everywhere I look is telling me that 2 is inclusive in the set of totatives of 36, but it doesn't seem to be the case for other even numbers.

Thanks.

Edit

Thanks for the responses. I suppose I am confused because I can't figure out the 12th totient from 1 to 36 inclusive.

Prime numbers from 0 to 36 include 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Querying wolfram alpha or a number of other sites yields the result that 36 has a totient of 12, the same number of primes I listed above -- but again, 2 should not be included in this count. I must be missing something (i.e. another relative prime) to have found a totient of only 11 in my verification. What am I missing?

share|improve this question
3  
Where have you seen $2$ included in the totatives of $36$? It isn’t one. –  Brian M. Scott Oct 22 '11 at 20:13
6  
Where did you look to tell you that $2$ is a relatively prime to 36? It's not. –  Arturo Magidin Oct 22 '11 at 20:13
    
Perhaps your sources are listing 2 among the divisors of 36. –  Austin Mohr Oct 22 '11 at 20:21
    
This is probably one of such pages isn't? –  Quixotic Oct 22 '11 at 21:02
    
Thank you all for your responses. Please see my edit. –  Brian D Oct 23 '11 at 1:02

3 Answers 3

up vote 5 down vote accepted

You're confusing prime with relatively prime.

Thanks for the responses. I suppose I am confused because I can't figure out the 12th totient from 1 to 36 inclusive.

Prime numbers from 0 to 36 include 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

You don't pretend that 1 is prime in this context, you recognize that gcd(1,36) = 1 and so 1 is relatively prime to 36. So the relevant list isn't the one you give, it's

sage: [k for k in [1..36] if gcd(k,36) == 1]
[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35]
sage: len([k for k in [1..36] if gcd(k,36) == 1])
12

Does that make sense?

share|improve this answer
    
Yes, it does. Thanks for clarifying! –  Brian D Oct 23 '11 at 7:01

From here:

A totative is a positive integer less than or equal to a number which is also relatively prime to , where $1$ is counted as being relatively prime to all numbers.

Another way of putting that is for any $a,b \in \mathbb{N}$ and $a<b$, $a$ is a totative of $b$ iff $(a,b)=1$.In this case as $(2,36) \neq 1 \Rightarrow$ $2$ is not a totative of $36$.


ADDED (after the question edit):

When finding all totatives of a number (say $N$),we don't (necessarily) need to think about prime numbers at all,what we need is to find all of the relatively prime numbers between [1,N).And we know that $1$ is relatively prime to any number in $\mathbb{N}$.Hence the result.

share|improve this answer
    
This was my understanding. Please see my edits above. –  Brian D Oct 23 '11 at 1:02
1  
@Brian D:I see you already understood the concept,anyways I modified the answer to your needs :) –  Quixotic Oct 23 '11 at 8:01
    
Actually looking back I don't think I understood then.. haha but now I get it. Thanks! –  Brian D Oct 23 '11 at 20:46
    
@Brian D:Aha,Glad to help :) –  Quixotic Oct 23 '11 at 20:59

You are confusing "prime" and "relatively prime."

Two positive integers $a$ and $b$ are "relatively prime" if and only if there is no prime that divides both. Equivalently, if the greatest common divisor of $a$ and $b$ is $1$.

A positive integer $p$ is a prime if and only if $p\neq 1$, and whenever $p$ divides a product $xy$, it follows that $p$ divides $x$ or $p$ divides $y$.

The totatives of $n$ are the integers $a$ such that $1\leq a\lt n$ and $\gcd(a,n)=1$; that is, that are relatively prime to $n$; not the primes that are smaller than $n$. If $p$ is a prime strictly smaller than $n$, then there are two possibilities: $p$ divides $n$, or else $p$ is a totative of $n$. So primes smaller than $n$ often account for several of the totatives of $n$, but they are not all the totatives.

So, the positive integers less than $36$ are:

  • 1: $\gcd(1,36) = 1$, so $1$ is a totative of $36$.
  • 2: $\gcd(2,36) = 2$, so $2$ is not a totative of $36$.
  • 3: $\gcd(3,36) = 3$;
  • 4: $\gcd(4,36) = 4$;
  • 5: $\gcd(5,36) = 1$;
  • 6: $\gcd(6,36) = 6$;
  • 7: $\gcd(7,36) = 1$;
  • 8: $\gcd(8,36) = 4$;
  • 9: $\gcd(9,36) = 9$;
  • 10: $\gcd(10,36) = 2$;
  • 11: $\gcd(11,36) = 1$;
  • 12: $\gcd(12,36) = 12$;
  • 13: $\gcd(13,36) = 1$;
  • 14: $\gcd(14,36) = 2$;
  • 15: $\gcd(15,36) = 3$;
  • 16: $\gcd(16,36) = 4$;
  • 17: $\gcd(17,36) = 1$;
  • 18: $\gcd(18,36) = 18$;
  • 19: $\gcd(19,36) = 1$;
  • 20: $\gcd(20,36) = 4$;
  • 21: $\gcd(21,36) = 3$;
  • 22: $\gcd(22,36) = 2$;
  • 23: $\gcd(23,36) = 1$;
  • 24: $\gcd(24,36) = 12$;
  • 25: $\gcd(25,36) = 1$;
  • 26: $\gcd(26,36) = 2$;
  • 27: $\gcd(27,36) = 9$;
  • 28: $\gcd(28,36) = 4$;
  • 29: $\gcd(29,36) = 1$;
  • 30: $\gcd(30,36) = 6$;
  • 31: $\gcd(31,36) = 1$;
  • 32: $\gcd(32,36) = 4$;
  • 33: $\gcd(33,36) = 3$;
  • 34: $\gcd(34,36) = 2$;
  • 35: $\gcd(35,36) = 1$.

So the totatives of 36 are: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35. Of these, 1, 25, and 35 are not prime numbers, but they are relatively prime to $36$. Of the primes smaller than $36 = 2^2\times 3^2$, neither $2$ nor $3$ are totatives of $36$.

share|improve this answer
    
Awesome Arturo. This was very helpful. I've got to give it to DSM for answering first, but I +1'd you for the very thorough explanation. Thank you. –  Brian D Oct 23 '11 at 7:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.