1
$\begingroup$

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?

  • 0
    Neither $2$ nor $3$ are totatives.2011-10-23

3 Answers 3

4

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

  • 0
    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.2011-10-23
5

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, $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.

  • 0
    @Brian D:Aha,Glad to help :)2011-10-23
5

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?

  • 0
    Yes, it does. Tha$n$ks for clarifyi$n$g!2011-10-23