1
$\begingroup$

Euler's totient function of n gives us the number of integers coprime to n that are less than or equal to n and greater than or equal to 1. Clearly the arithmetic progression {d, 2d, ..., nd} with common difference d and length n has a count of integers coprime to n equal to the totient function of n if d is already coprime to n. However I am having trouble proving that any arithmetic progression is also equal to totient function of n. That is, why is the count of integers coprime to n for {a+d, a+2d, ..., a+nd} the same as the totient function of n, where a can be any integer and d is coprime to n? I tried both simple and strong induction but it doesn't work.

$\endgroup$
0
$\begingroup$

To tackle this problem, we will use three facts.

1) Look at {$d, 2d, \cdots, nd$} (mod $n$). Then since $n$ is coprime to $d$, this will be simply a permutation of {$1, 2, \cdots, n$} [e.g., we can go from the first to the second by multiplying by $d^{-1}$ (mod $n$)].

2) {$a+1, a+2, \cdots, a+n$} is also a permutation of {$1, 2, \cdots, n$} (mod $n$). [e.g., we can go from the first to the second by adding $-a$ (mod $n$)].

3) Given $k\in\Bbb Z$, $a + kn$ is coprime to $n$ if and only if $a$ is.

Proof: Suppose $a$ is NOT coprime to $n$. Then there exists $c=$GCD($a, n$)$>1$ so that $a = cd$ and $n=ce$ for some $d, e\in\Bbb N$. Then $a+kn=cd+kce = c(d+ke)$, and $n=ce$; so $c>1$ divides the GCD($a+kn,n$), and so $a+kn$ is NOT coprime to $n$.

Conversely, if $a+kn$ is NOT coprime to $n$ then let $a'=a+kn$. By the argument above, $a'+(-k)n=a$ is NOT coprime to $n$ as well. Therefore, $a$ is coprime to $n$ iff $a+kn$ is coprime to $n$.

This implies that we can reduce a set (mod $n$) without affecting the number of integers that are coprime to $n$. So, let us count the number of integers in {$a+d, a+2d, \cdots, a+nd$} coprime to $n$.

  • Since given $k\in\Bbb Z$, $a+kn$ is coprime to $n$ if and only if $a$ is coprime to $n$, then this number will equal the number of integers in {$a+d, a+2d, \cdots, a+nd$} (reduced mod $n$) coprime to $n$.

  • Since {$a+d, a+2d, \cdots, a+nd$} is a permutation of {$d, 2d, \cdots, nd$} (mod $n$), then this number will equal the number of integers in {$a+d, a+2d, \cdots, a+nd$} (reduced mod $n$) coprime to $n$.

  • Since {$d, 2d, \cdots, nd$} is a permutation of {$1, 2, \cdots n$} (mod $n$), then this number is equal to the number of integers in {$1, 2, \cdots, n$} coprime to $n$.

  • Therefore, by definition of $\phi(n)$, the number we are looking for equals $\phi(n)$.

$\endgroup$
  • $\begingroup$ Thanks, I think I updated my answer to reflect that. Let me know if this is still not enough. $\endgroup$ – Alex Dec 30 '15 at 19:30
  • $\begingroup$ I still do not understand. Could you explain the last paragraph a bit better? $\endgroup$ – John Robins Dec 30 '15 at 21:38
  • $\begingroup$ OK, I split it into 4 steps. Let me know if that doesn't make sense. $\endgroup$ – Alex Dec 30 '15 at 21:49
  • $\begingroup$ How do we know that a set over a mod will behave the same as a set without? $\endgroup$ – John Robins Dec 30 '15 at 21:54
  • $\begingroup$ By the comment that a+kn is coprime to n if and only if a is coprime to n. This is because: a is NOT coprime to n iff there exists b>1 so b|a and b|n. Then b|a+kn as well; so a+kn is not coprime to n as well. The converse is true by taking k=-k. $\endgroup$ – Alex Dec 30 '15 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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