ПЕРВООБРА́ЗНЫЙ КО́РЕНЬ

ПЕРВООБРА́ЗНЫЙ КО́РЕНЬ по мо­ду­лю $m$, на­ту­раль­ное чис­ло $g$ та­кое, что наи­мень­шее по­ло­жи­тель­ное чис­ло $k$, для ко­то­ро­го раз­ность $g^k-1$ де­лит­ся на $m$ ($g^k$ срав­ни­мо с 1 по мо­ду­лю $m$), сов­па­да­ет с $φ(m)$, где $φ(m)$ – чис­ло на­ту­раль­ных чи­сел, мень­ших $m$ и вза­им­но про­стых с $m$. Напр., при $m$=7 П. к. по мо­ду­лю 7 яв­ля­ет­ся чис­ло 3. Дей­ст­ви­тель­но, $φ(7)$=6; чис­ла 3¹-1=2, 3²-1=8, 3³-1=26, 3⁴-1=80, 3⁵-1=242 не де­лят­ся на 7, лишь 3⁶-1= 728 де­лит­ся на 7.

П. к. су­ще­ст­ву­ют, ко­гда $m$=2, $m$=4, $m=p^α$ , $m= 2p^α$ , где $p$ – про­стое не­чёт­ное чис­ло, $α⩾1$ – це­лое, а для др. мо­ду­лей их нет. Чис­ло П. к. в этих слу­ча­ях рав­но $φ[φ(m)]$ (чис­ла, раз­ность ко­то­рых крат­на $m$, не счи­та­ют­ся за раз­лич­ные). И. М. Ви­но­гра­дов