Content deleted Content added
→Divisor sum: Minor wording |
|||
Line 114:
where the sum is over all positive divisors {{mvar|d}} of {{mvar|n}}, can be proven in several ways. (See [[Arithmetical function#Notation|Arithmetical function]] for notational conventions.)
One proof is to note that {{math|''φ''(''d'')}} is also equal to the number of possible generators of the [[cyclic group]] {{math|''C''<sub>''d''</sub>}} ; specifically, if {{math|''C''<sub>''d''</sub> {{=}} ⟨''g''⟩}} with {{math|1=''g''<sup>''d''</sup> = 1}}, then {{math|''g''<sup>''k''</sup>}} is a generator for every {{mvar|k}} coprime to {{mvar|d}}. Since every element of {{math|''C''<sub>''n''</sub>}} generates a cyclic [[subgroup]], and
The formula can also be derived from elementary arithmetic.<ref>Graham et al. pp. 134-135</ref> For example, let {{math|''n'' {{=}} 20}} and consider the positive fractions up to 1 with denominator 20:
| |||