7E (Numbers and Sets)

Let

M = {i : x \in A_{i}}

, with

∣ M ∣ = m

. Then

1_{A_{S}} (x) = 1

exactly when

S \subseteq M

, and the sum becomes

\sum_{s = t}^{m} (s m) (t s) (- 1)^{s - t} = (t m) \sum_{r = 0}^{m - t} (r m - t) (- 1)^{r} = (t m) (1 - 1)^{m - t} .

This is

1

when

m = t

and

0

otherwise. Summing over

x \in X

yields

# {x : x belongs to exactly t sets} = S \sum (t ∣ S ∣) (- 1)^{∣ S ∣ - t} ∣ A_{S} ∣.

Taking the complement of the

t = 0

∣ ⋃_{i} A_{i} ∣ = \sum_{\emptyset \neq = S} (- 1)^{∣ S ∣ + 1} ∣ A_{S} ∣.

p_{1}, \dots, p_{r}

are the distinct prime divisors of

N

, inclusion-exclusion removes their multiples from

{1, \dots, N}

and gives

φ (N) = N p ∣ N \prod (1 - \frac{1}{p}) .

For the stated squarefree

n = q_{1} \dots q_{k}

and

g cd (x, n) = 1

x^{q_{j} - 1} \equiv 1 (mod q_{j})

. Since

q_{j} - 1 ∣ n - 1

, every

q_{j}

divides

x^{n - 1} - 1

; their product does too. Thus $n$ is a Carmichael number.

 Ancestors (9)

There are no discussions about this article yet.

There are currently no matching articles.