diff options
| author | Cyril Cohen | 2019-07-11 00:13:44 +0200 |
|---|---|---|
| committer | GitHub | 2019-07-11 00:13:44 +0200 |
| commit | 4142d9866cfc12b767031ecc82a14ee62ccbb6ab (patch) | |
| tree | 2637600c46f5b906374baac5546a9f8938ebaeb6 | |
| parent | 2a0a00630785c616899abaa6fccb95ee76f751bf (diff) | |
| parent | c09c3c86b5eab6f16a67fdd9b70618741e0c1727 (diff) | |
Merge pull request #369 from thery/totient
totient for prime
| -rw-r--r-- | CHANGELOG_UNRELEASED.md | 2 | ||||
| -rw-r--r-- | mathcomp/ssreflect/prime.v | 3 |
2 files changed, 5 insertions, 0 deletions
diff --git a/CHANGELOG_UNRELEASED.md b/CHANGELOG_UNRELEASED.md index 3777a83..55f44e6 100644 --- a/CHANGELOG_UNRELEASED.md +++ b/CHANGELOG_UNRELEASED.md @@ -16,6 +16,8 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/). - Added functions `tuple_of_finfun`, `finfun_of_tuple`, and their "cancellation" lemmas. +- Added theorem `totient_prime` in `prime.v` + ### Changed - `eqVneq` lemma is changed from `{x = y} + {x != y}` to diff --git a/mathcomp/ssreflect/prime.v b/mathcomp/ssreflect/prime.v index 16e44e2..7d07293 100644 --- a/mathcomp/ssreflect/prime.v +++ b/mathcomp/ssreflect/prime.v @@ -1338,6 +1338,9 @@ move=> p_pr e_gt0; rewrite totientE ?expn_gt0 ?prime_gt0 //. by rewrite primes_exp // primes_prime // unlock /= muln1 pfactorK. Qed. +Lemma totient_prime p : prime p -> totient p = p.-1. +Proof. by move=> p_prime; rewrite -{1}[p]expn1 totient_pfactor // muln1. Qed. + Lemma totient_coprime m n : coprime m n -> totient (m * n) = totient m * totient n. Proof. |