Could anyone explain to me the proof for such a method of checking whether a number is primitive root or not http://zobayer.blogspot.com/2010/02/primitive-root.html

why should i check only certain numbers to be equal to one or not ?

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 174 |

2 | awoo | 168 |

3 | nor | 165 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | maroonrk | 162 |

5 | Um_nik | 162 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

Could anyone explain to me the proof for such a method of checking whether a number is primitive root or not http://zobayer.blogspot.com/2010/02/primitive-root.html

why should i check only certain numbers to be equal to one or not ?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 15:56:19 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Since

nis a prime, we know thatg^{φ(n)}=g^{n - 1}= 1. We want to know if there is another exponente<n- 1 such thatg^{e}= 1.Let

ebe the smallest, positive integer withg^{e}= 1. This means that the exponents that give 1 are exactly 0,e, 2e, 3e, .... This means thatedividesn- 1. Ifeis really smaller thann- 1, then there must exist a prime factorpofn- 1, such thatestill divides . Which means that .So it is sufficient to check if any of the terms , with

pprime andp|n- 1, is equal to 1.