[Agda] Data.Nat.Primality.Prime and irreducibility
Sergei Meshveliani
mechvel at botik.ru
Fri Mar 6 10:46:21 CET 2015
On Fri, 2015-03-06 at 12:49 +0530, N. Raghavendra wrote:
> Hi,
>
> I am looking at the type
>
> Irreducible : ℕ → Set
> Irreducible n = n ≢ 1 × ((x y : ℕ) → n ≡ x * y → x ≡ 1 ⊎ y ≡ 1)
>
> I am able to prove
>
> primen⇒irreduciblen : (n : ℕ) →
> Data.Nat.Primality.Prime n → Irreducible n
>
> I've some questions:
>
> 1. Is there a short proof of this implication? The one I wrote is a bit
> long.
>
> 2. How does one prove the converse of the above implication?
>
> 3. Is there some special reason for defining Prime as in
> Data.Nat.Primality, instead of something like
>
> Prime : ℕ → Set
> Prime n = n ≢ 1 × ((x y : ℕ) → n | x * y → n | x ⊎ n | y)
>
> as is common in informal mathematics?
>
> Thanks and cheers,
> Raghu.
>
Personally, I use a generic primality definition for any GCDRing
(an integral ring with GCD):
IsPrime : C → Set (α ⊔ α=)
IsPrime a = a ≉ 0# × ¬ Invertible a ×
(∀ {x y} → (x * y ≈ a) → Invertible x ⊎ Invertible y),
which, I think, is the classical definition.
Then, I prove several lemmata about possible Factorization structure for
the elements of such a ring, and find that this my definition works all
right.
Regards,
------
Sergei
More information about the Agda
mailing list