Qualcuno mi potrebbe dire cosa sono le permutazioni modulo m (o linkare dove vengono spiegate) e come si potrebbero usare?
Permutazioni TdN
Permutazioni TdN
L'argomento è stato tirato fuori da Drago qui http://forum.olimato.org/primi-e-potenze-t146.html
Qualcuno mi potrebbe dire cosa sono le permutazioni modulo m (o linkare dove vengono spiegate) e come si potrebbero usare?
Qualcuno mi potrebbe dire cosa sono le permutazioni modulo m (o linkare dove vengono spiegate) e come si potrebbero usare?
Re: Permutazioni TdN
Spero che qualcuno piu informato di me intervenga,dato che dell'argomento non ne so nulla, in ogni caso:
1. non credo esistano studi sulle permutazione modulo qualcosa, percio direi che la situazione va analizzata come caso particolare
2. non so dove trovare altre risorse,comunque puoi trovare un introduzione poco approfondita nelle dispense di matematica olimpionica alla fine del capitolo di combinatoria, ma ripeto è trattato in modo davvero basilare.
1. non credo esistano studi sulle permutazione modulo qualcosa, percio direi che la situazione va analizzata come caso particolare
2. non so dove trovare altre risorse,comunque puoi trovare un introduzione poco approfondita nelle dispense di matematica olimpionica alla fine del capitolo di combinatoria, ma ripeto è trattato in modo davvero basilare.
Re: Permutazioni TdN
Allora, se abbiamo un insieme $S:=\{a_1,\dots,a_n\}$ e una funzione $f: S\to S$, diciamo che $f$ è una permutazione se è biiettiva; in pratica una permutazione riordina gli elementi di un insieme.
Ora, dato un insieme $S$ di $n$ elementi, diciamo che è un sistema completo di residui se $S\mod n$ è isomorfo a $\mathbb Z/n\mathbb Z$, ovvero se gli elementi dell'insieme ridotti modulo $n$ sono tutti distinti (e quindi essendo $n$ coprono tutti i possibili resti).
E' facile vedere che se $S$ è un sistema completo, allora anche $aS+b$, con $(a,n)=1$, è un sistema completo (infatti $ax+b\equiv ay+b\pmod n\iff x\equiv y\pmod n$)
Allora detta $f(x)=ax+b$, possiamo dire che è una permutazione degli interi modulo $n$ se e solo se $(a,n)=1$; quindi applicando la funzione a ogni elemento di $\mathbb Z/n\mathbb Z$ otteniamo un suo riordinamento.
Poi ovviamente ci sono molte altre funzioni che possono essere considerate come permutazioni modulo qualcosa, particolarmente quando il modulo è primo.
Inoltre, quando il modulo è primo, ci sono parecchie cose belle, tipo il fatto che per ogni $i=1,2,\dots,p-1$ la funzione $f(x)=ix$ è una permutazione.
Nel caso che hai linkato la funzione è $f(x)=2x$ ed essendo il modulo primo e quindi dispari, questa è una permutazione.
Perchè l'ho citata? Perchè si dimostra in generale (non è difficile usando il produttone per ottenere il segno di una permutazione), che detta $\sigma(i)=ai$ con $(a,p)=1$, che è una permutazione, allora $\text{sgn}(\sigma)=\left(\frac a p\right)$
Ora, dato un insieme $S$ di $n$ elementi, diciamo che è un sistema completo di residui se $S\mod n$ è isomorfo a $\mathbb Z/n\mathbb Z$, ovvero se gli elementi dell'insieme ridotti modulo $n$ sono tutti distinti (e quindi essendo $n$ coprono tutti i possibili resti).
E' facile vedere che se $S$ è un sistema completo, allora anche $aS+b$, con $(a,n)=1$, è un sistema completo (infatti $ax+b\equiv ay+b\pmod n\iff x\equiv y\pmod n$)
Allora detta $f(x)=ax+b$, possiamo dire che è una permutazione degli interi modulo $n$ se e solo se $(a,n)=1$; quindi applicando la funzione a ogni elemento di $\mathbb Z/n\mathbb Z$ otteniamo un suo riordinamento.
Poi ovviamente ci sono molte altre funzioni che possono essere considerate come permutazioni modulo qualcosa, particolarmente quando il modulo è primo.
Inoltre, quando il modulo è primo, ci sono parecchie cose belle, tipo il fatto che per ogni $i=1,2,\dots,p-1$ la funzione $f(x)=ix$ è una permutazione.
Nel caso che hai linkato la funzione è $f(x)=2x$ ed essendo il modulo primo e quindi dispari, questa è una permutazione.
Perchè l'ho citata? Perchè si dimostra in generale (non è difficile usando il produttone per ottenere il segno di una permutazione), che detta $\sigma(i)=ai$ con $(a,p)=1$, che è una permutazione, allora $\text{sgn}(\sigma)=\left(\frac a p\right)$
Re: Permutazioni TdN
ok la prossima volta evito di sparare a caso