Percorso più breve in aritmetico modulare

Question

Supponiamo di avere 7 vertici, ognuno dei quali corrisponde a un diverso modulo Integer sette.Il bordo esiste tra due vertici x e y se X + 3 ≡ y mod 7. Ad esempio, c'è un bordo tra 0 e 3 e un bordo tra 5 e 2. Qual è la lunghezza del percorso più breve tra 0 e 1?

Il mio metodo per ottenere la risposta è applicare la definizione di congruenza.Il bordo uscita IFF $ 7 |X + 3 - Y $ .Pertanto, ho ottenuto un grafico ciclico e quindi ottenere la risposta è 2. C'è qualche metodo che posso giocare con aritmetica modulare senza disegnare un grafico in modo da poter ottenere un percorso più breve tra il nodo 0 e il nodo 1?

Answer 1

Consideriamo il caso più generale in cui hai $ n $ vertici e colleghi $ x, y $ se $ xy \ equiv a \ pmod {n} $ (nel tuo caso, $ n= 7 $ e $ a= 3 $ ).

Il tuo grafico è un sindacato di cicli disgiunti. Quando $ N $ è Prime (come nel tuo caso), è un singolo ciclo. Quindi se vuoi ottenere da $ x $ a $ y $ , o continui ad aggiungere <="container di matematica"> $ A $ (Modulo $ N $ ), di te continui a sottrarre $ A $ (Modulo $ N $ ). Se aggiungi $ m $ volte il valore $ a $ (dove $ m $ è probabilmente negativo) quindi $ x + mA \ equiv y \ pmod {n} $ , cioè, $ mA \ equiv yx \ pmod {n} $ . Assumiamo ora che $ (A, n)= 1 $ (ad esempio, $ n $ è Prime e $ 1 \ Leq A \ Leq N-1 $ ). Quindi $ M \ Equiv A ^ {- 1} (y-x) \ pmod {n} $ .

Risolvere l'equazione sopra (supponendo $ x \ non \ equiv y \ pmod {n} $ ), ci sarà una soluzione $ M _ + $ Nella gamma $ 1, \ Ldots, n-1 $ e un altro contenitore $ m _- $ nella gamma $ - 1, \ Ldots, - (n-1) $ . La distanza è $ \ min (m _ +, - m _-) $ .

Nel tuo caso, $ n= 7 $ e $ a= 3 $ . Possiamo calcolare $ a ^ {- 1}= 5 $ . Se $ x= 0 $ e $ y= 1 $ quindi $ a ^ {- 1} (yx)= 5 $ e così $ m_ += 5 $ e $ - M_-= 2 $ . Quindi il percorso più breve va all'indietro per due passaggi: $ 0 \ a 4 \ to 1 $ .

Answer 2

È necessario trovare numeri interi $ A $ e $ B $ in modo tale da

$ 3a= 7b + 1 $

e da tutti i valori (infinitamente molti) di $ A $ tu vuoi quello che minimizza $ | A | $ . In questo caso, possiamo vedere per prova e errore che il set di soluzioni è $ a= 5 + 7n $ per i valori interi di $ N $ e per ridurre al minimo $ | A | $ Prendiamo $ n= -1 $ , in modo che $ a= -2 $ e il percorso più breve è $ 0 \ a 4 \ to 1 $ .

In generale, ci saranno infinitamente molte soluzioni a $ PA= QB + 1 $ Finché $ P $ e $ q $ sono co-prime (non condividere fattori comuni diversi da $ 1 $ ), e puoi usare il algoritmo euclideo per trovare il valore positivo più piccolo della classe $ a $ . Se il più piccolo valore positivo di $ A $ è $ a_0 $ quindi il valore di $ A $ che minimizza $ | A | $ è $ A_0 $ o $ a_0 - q $ .

Answer 3

Possiamo facilmente generalizzare questo problema: dato un gruppo finito G, due elementi G e H in G, e un sottoinsieme S di G, trova il percorso più breve da G a H nel grafico i cui vertici sono gli elementi di G e i cui bordi sono gli elementi delle S o le rispettive avversiste degli elementi di S, cioè, due vertici x e Y sono adiacenti se e solo se y= xr per qualche r che è un elemento di s o è inverso di qualche elemento di S. Nota che questo grafico ha | g | Verticanti e | S || G | Bordi in un'implementazione di computer esplicita o implicita. Un semplice algoritmo di ricerca di larghezza di ampiezza su questo grafico iniziando dal vertice G e terminando una volta raggiunto il vertice h, produrrà il percorso più breve tra G e H in tempo o (| G | + | S || G |)= O ( | S || G |) Tempo. Inoltre, non dobbiamo effettivamente costruire questo grafico; Questo perché sappiamo già cosa sono tutti i bordi. Dobbiamo solo andare in giro attraverso i vicini dell'attuale elemento del Gruppo ad ogni iterazione del primo algoritmo di ricerca di ampiezza.

Nel tuo caso, per qualsiasi numero intero positivo n, abbiamo s= {3 mod n} e che l'ordine del gruppo additivo di classi di residue mod n è n, quindi possiamo trovare il percorso più breve tra due residui specificati Lezioni mod n in o (n)= o (n) tempo.