Information Technology Reference
In-Depth Information
n
k
=
0
n
k
2
n
=
.
Newton's formula is the starting point of a lot of important mathematical theorems.
An example is the following
Fermat's little theorem
which follows easily by in-
duction from Newton's formula. It is an important property of modular arithmetic,
based on congruences. Notation
n
m
mod
k
denotes the
congruence
of
n
and
m
modulo
k
, holding when the divisions of
n
and
m
by
k
provides the same remainder.
≡
Proposition 7.2 (Fermat's little Theorem).
If p is a prime number then, for any
x
∈
N
:
x
p
≡
xmodp
Proof
p
k
x
k
n
k
=
0
p
(
x
+
1
)
=
in the right side of the equation, apart 1 and
x
p
, other terms have coefficients with
the following forms with 1
<
j
<
p
:
p
!
/
(
j
!
(
p
−
j
)
!
)
and, due to the primality of
p
, the factor
p
cannot be removed from the numerator,
therefore they are congruent to zero modulo
p
. In conclusion, for
x
1 the equation
of the proposition trivially holds, then if we assume that it holds for a value
x
,then
we have:
=
p
x
p
(
x
+
1
)
≡
+
1mod
p
but, by induction:
x
p
≡
x
mod
p
therefore:
x
p
+
1
≡
x
+
1mod
p
and, by the transitive property of equality, this implies:
p
(
x
+
1
)
≡
x
+
1mod
p
.
7.2
Distributions and Discrete Probability
Diagrams 7.1 e 7.2 are a kind of discrete version of Gaussian distribution shown
in Fig. 7.3. This corresponds to the fact that by using Stirling approximation, ex-
plained in the next section, it is possible to obtain a formula, due to De Moivre and
Laplace, which approximates the binomial coefficients with a bell-shaped curve,
usually called
gaussian
because Gauss showed its deep probabilistic meaning. In
fact, if we consider the Bernoulli's law of two possible events, say
{
1
,
0
}
, of proba-
bilities
p
and
q
=
1
−
p
, respectively, then the probability
p
(
n
,
k
)
of having
k
times
1in
n
events is given by:
