|
Bit rješenja je da imaš sustav kongruencija [tex]x \equiv 0,1 (mod (p_i))[/tex] za svaki mogući prosti faktor [tex]p_i[/tex] - to dobivaš iz raspisa da [tex]n | x(x-1)[/tex] za [tex]2 \leq x \leq n-1[/tex] (dvojka je tu iz tehničkih razloga). Takvih rješenja, ako je prostih faktora [tex]k[/tex], sveukupno [tex]2^k[/tex] i konstruiraš ih uz pomoć Kineskog teorema o ostacima (pošto imaš [tex]k[/tex] jednadžbi, a prosti brojevi (odnosno ideali generirani njima) su međusobno relativno prosti).
To je za slučaj kada je [tex]n[/tex] složen broj. Inače su jedina rješenja ona trivijalna koja vrijede za oba slučaja - [tex]x=0,1[/tex]. :)
P. S. OK, možeš ignorirati ovu gore granicu da je [tex]2 \leq x[/tex], više-manje je bespotrebna. :) Meni je trebala u rješenju... :P
Bit rješenja je da imaš sustav kongruencija [tex]x \equiv 0,1 (mod (p_i))[/tex] za svaki mogući prosti faktor [tex]p_i[/tex] - to dobivaš iz raspisa da [tex]n | x(x-1)[/tex] za [tex]2 \leq x \leq n-1[/tex] (dvojka je tu iz tehničkih razloga). Takvih rješenja, ako je prostih faktora [tex]k[/tex], sveukupno [tex]2^k[/tex] i konstruiraš ih uz pomoć Kineskog teorema o ostacima (pošto imaš [tex]k[/tex] jednadžbi, a prosti brojevi (odnosno ideali generirani njima) su međusobno relativno prosti).
To je za slučaj kada je [tex]n[/tex] složen broj. Inače su jedina rješenja ona trivijalna koja vrijede za oba slučaja - [tex]x=0,1[/tex]. 
P. S. OK, možeš ignorirati ovu gore granicu da je [tex]2 \leq x[/tex], više-manje je bespotrebna. Meni je trebala u rješenju... 
|
