Kongruenser - Wilsons Sats

Wilson's Theorem: Let p be a prime number. Then $(p - 1)! \equiv - 1 m o d p$ .

Use Wilson’s Theorem to ﬁnd the least nonnegative residue modulo m of the integer n below.

$n = 31! / 22!$ , $m = 11$

Jag har försökt att vända och vrida på detta på olika vis för att med hjälp av satsen komma fram till svaret, utan framgång. Någon som kan hjälpa mig på traven lite? En tidigare deluppgift hade $n = 21!$ och $m = 23$ . Då löste jag den genom att skriva

$22 * 21! \equiv 22 (m o d 23) \Rightarrow 21! \equiv 1 (m o d 23)$

Det gäller att

$\frac{31!}{22!} = 23 \cdot 24 \dots 30 \cdot 31$

Vad är 23, 24, 25,..., 30, 31 mod 11?

Jag antar att satsen i detta fallet är onödig i så fall?

$23 \equiv 1 m o d 11 24 \equiv 2 m o d 11 25 \equiv 3 m o d 11 ⋮ 31 \equiv 9 m o d 11$

$\Rightarrow \frac{31!}{22!} \equiv 9! m o d 11 \equiv 2^{7} * 3^{4} * 5 * 7 m o d 11 \equiv 128 * 81 * 35 m o d 11 \equiv 7 * 4 * 2 m o d 11 \equiv 56 m o d 11 \equiv 1 m o d 11$

Svaret är alltså 1.

Edit:

Kom på att jag kan nyttja satsen genom att se att

$10! = 10 * 9! \equiv 10 m o d 11 \equiv 1 m o d 11$

Nej jag skulle inte säga att den är onödig. Eftersom $10^{2} \equiv (- 1)^{2} \equiv 1 (m o d 11)$ så får man att

$\frac{31!}{22!} \equiv 9! \equiv 9! \cdot 10^{2} \equiv 10! \cdot 10 \equiv - 1 \cdot 10 \equiv 1 (m o d 11)$

Svara

Visa senaste svar