(Lucas’ criterion) If the prime p divides Fm, where m ≥ 2, then p = k 2^(m+2)+1 for some positive integer k.
Published On :2021-08-09 16:25:00
Proof that If the prime p divides Fm, where m ≥ 2, then p = k 2^(m+2)+1 for some positive integer k.
[begin{array}{l} (Lucas;criterion)If;the;prime;p;divides;{F_m},where;m ge 2,then;\ p = k{2^{(m + 2)}} + 1for;some;positive;integer;k.\\ Proof.\\ Let;b = {2^{({2^{(m - 2)}})}}({2^{({2^{(m - 1)}})}} - 1).;Since\\ (1)\ {2^{{2^m}}} + 1 equiv 0;left( {mod;;p} right)\\ We;{rm{ }}have\\ (2)\ {b^2} = {2^{{2^{m - 1}}}}left( {{2^{{2^m}}} - 2 times {2^{{2^{m - 1}}}} + 1} right) equiv - 2 times {2^{{2^m}}}\ equiv - 2 times {2^{{2^m}}} + 2left( {{2^{{2^m}}} + 1} right) equiv 2;;;;left( {;mod;;p} right)\\ From;{rm{ }}this;{rm{ }}it;{rm{ }}follows{rm{ }};that\\ {b^{{2^{m + 1}}}} equiv {2^{{2^m}}} equiv - 1;;;left( {mod;;p} right)\\ And;{rm{ }}thus\\ {b^{{2^{m + 2}}}} equiv 1;;;left( {mod;;p} right)\\ Consequently,;according;to;Multiplicative;Order,\;;or{d_p}b = {2^j}for;some;j = m + 2.\\ However,;;if;j; < m + 2,and;so;;;m + 1 - j = 0,;;then,\\ 0 equiv 1 - 1 = {left( {{b^{{2^j}}}} right)^{{2^{m + 1 - {rm{j}}}}}} - 1 = {b^{{2^{m + 1}}}} - 1;;; equiv {2^{{2^m}}} - 1;;;left( {mod;;p} right)\\\ Which{rm{ }};contradicts{rm{ }};with{rm{ }};the{rm{ }};statement{rm{ }}left( 1 right).{rm{ }};Hence,\\ (3)\ or{d_p}b = {2^{m + 2}}\\ The;numbers;p;and;b;are;coprime;due;to;statement;(2).\ Therefore,;;applying;Fermat's;little;theorem,\;;i.e.;;{b^{(p - 1)}} = 1(mod;p),; and;using;Multiplicative;Order\;and;statement;(3),we;obtain;\\ p - 1 = k;or{d_p}b = ;k{2^{m + 2}}.\\ Hence;;p = k{2^{(m + 2)}} + 1.\\\ 'See{rm{ }}left( {Krizek,{rm{ }}2001,p.82} right)' end{array}]