write fundamental theorem of arithmatics
Answers
Answer:
The fundamental theorem of arithmetic states that every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes (Hardy and Wright 1979, pp. 2-3). This theorem is also called the unique factorization theorem.
Step-by-step explanation:
As usual the main difficulty is uniqueness; we assume existence throughout.
So, to prove uniqueness, go by induction: suppose
n
=
p
1
…
p
r
=
q
1
…
q
s
for some
n
>
1
, where the statement has been proven for
m
=
1
,
…
,
n
−
1
.
In particular, if
m
∈
[
1
,
n
−
1
]
is divisible by a prime
p
, then
p
appears in the (unique!) prime factorization of
m
. Call this fact (+).
Key idea
Instead of directly using Euclid's lemma to prove that one of the
q
j
's is divisible by
p
1
(hence equal to
p
1
), we take an indirect route to the same end. We will assume
p
1
is the smallest prime among the
p
i
,
q
j
and then reduce some
q
j
's modulo
p
1
(which doesn't affect divisibility by
p
1
).
Details
If
q
1
=
p
1
, we're done by the inductive hypothesis for
n
/
p
1
.
Else, by the minimality assumption on
p
1
, we have
p
1
<
q
1
. Then
m
=
(
q
1
−
p
1
)
q
2
…
q
s
is congruent to
q
1
q
2
…
q
s
=
n
≡
0
(
mod
p
1
)
.
Now, by (+),
p
1
appears in the (unique!) prime factorization of
m
. Upon choosing a prime factorization of
q
1
−
p
1
(by existence), we conclude that either
q
1
−
p
1
is divisible by
p
1
(in which case
p
1
∣
q
1
, so
q
1
=
p
1
), or one of
q
2
,
…
,
q
s
is divisible by (hence equal to)
p
1
. As in the
q
1
=
p
1
case, we're now done by the inductive hypothesis for
n
/
p
1
.
Reflection
We didn't need to choose
p
1
to be absolutely minimal among the
p
i
,
q
j
; assuming
p
1
≤
q
1
would still have worked. Also, in the second (interesting) case
p
1
<
q
1
above, it is actually impossible for
q
1
−
p
1
to be divisible by
p
1
, or else
q
1
would have to be a multiple of
p
1
, which would be inconsistent with the primality of
q
1
.
Answer:
fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1[3] either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.[4][5][6] For example,
1200 = 24 × 31 × 52 = 2 × 2 × 2 × 2 × 3 × 5 × 5 = 5 × 2 × 5 × 2 × 3 × 2 × 2 = ...
The theorem says two things for this example: first, that 1200 can be represented as a product of primes, and second, that no matter how this is done, there will always be exactly four 2s, one 3, two 5s, and no other primes in the product.
The requirement that the factors be prime is necessary: factorizations containing composite numbers may not be unique (e.g., 12 = 2 × 6 = 3 × 4).
This theorem is one of the main reasons why 1 is not considered a prime number: if 1 were prime, then factorization into primes would not be unique; for example, 2 = 2 × 1 = 2 × 1 × 1 = ...