સમશેષતા (congruence) : બે કે વધુ પૂર્ણાંકોને એક વિશેષ પૂર્ણાંક વડે ભાગતાં સરખી શેષ વધવાનો ગુણધર્મ. 25 અને 11ને સાત વડે ભાગતાં એકસરખી (4) શેષ વધે છે, તેથી 7 માટે 25 અને 11 સમશેષ છે તેમ કહેવાય. આમાં 7ને સમશેષતાનો માનાંક (modulus) કહેવાય અને 25 દ્ર 11 (mod 7) એમ લખાય છે. નીચેનાં વિધાનો સમાનાર્થી છે :
(1) a દ્ર b (mod m)
(2) a b દ્ર 0 (mod m)
(3) m તે a bનો અવયવ છે.
કોઈ નિશ્ચિત માનાંક માટે સમશેષતાનો સંબંધ પૂર્ણાંકગણ Z માટે સામ્યસંબંધ છે, એટલે કે,
(1) પ્રત્યેક a ીં Z માટે a દ્ર a
(2) બધા a, b ીં Z માટે જો a દ્ર b તો b દ્ર a
(3) a, b, c ીં Z માટે જો a દ્ર b તથા b દ્ર c તો a દ્ર c.
વળી સમશેષતાનો આ સંબંધ સરવાળા અને ગુણાકારની ક્રિયાઓ સાથે સુસંગત છે, એટલે કે,
જો a દ્ર b તથા c દ્ર d તો a + b દ્ર c + d તથા ac દ્ર bd.
આના વિશેષ કિસ્સા તરીકે પ્રત્યેક પૂર્ણાંક n માટે જો a દ્ર b તો na દ્ર nb તથા પ્રત્યેક અનૃણ પૂર્ણાંક m માટે an દ્ર bn થાય. જો f(x) પૂર્ણાંક સહગુણકોવાળી બહુપદી હોય,
f(x) = pnxn + pn1 xn1 + … + p1x + p0, p1, ીં Z, તથા a દ્ર b (mod m) તો f(a) દ્ર f(b) (mod m).
ફરમાનું પ્રમેય : ફરમાએ સાબિત કર્યું હતું કે જો p અવિભાજ્ય હોય તથા p તે aનો અવયવ ન હોય તો ap1 દ્ર 1 (mod p).
આ પ્રમેયનું એક સ્વરૂપ એવું પણ છે કે p અવિભાજ્ય હોય તો પ્રત્યેક a માટે ap દ્ર a (mod p).
વિલ્સનનું પ્રમેય : જો p અવિભાજ્ય હોય તો
(p 1) ! દ્ર 1 (mod p).
આ પ્રમેયનું પ્રતીપ પણ સાચું છે.
પૂર્ણ અને સંક્ષિપ્ત શેષસંહતિઓ (complete and reduced residue systems) : આગળ જણાવ્યા પ્રમાણે, સમશેષતા એ સામ્યસંબંધ છે; તેથી તેના વડે પૂર્ણાંક ગણ Zના સામ્યવર્ગો (equivalence classes) પડી જાય છે. માનાંક m માટે સામ્યવર્ગોની સંખ્યા પણ m હોય છે. આ સામ્યવર્ગો નીચે પ્રમાણે હોય છે :
C0 = {0, ણ્ m, ણ્ 2m, ણ્ 3m, …}
C1 = {1, ણ્ mH, ણ્ 2m + 1, ણ્ 3m + 1, …}
C2 = {2, ણ્ m + 2, ણ્ 2m + 2, ણ્ 3m + 2, …}
– – – – – – – – – – – – – – – – – – – – – – – – – –
Cm1 = {m 1, ણ્ m + (m 1), ણ્ 2m + (m 1), ણ્ 3m + (m 1), …}
દા.ત., m = 3 માટે આ વર્ગો C0 = {0, ણ્ 3, ણ્ 6, ણ્ 9, …}, C1 = {…, 5, 2, 1, 4, 7, 10, 13, …} તથા C2 = {…, 4, 1, 2, 5, 8, …} છે.
જો m ભિન્ન પૂર્ણાંકોના કોઈ ગણમાં m પૈકી દરેક સામ્યગણનો એક એક સભ્ય હોય તો તેવા ગણને (m માટેની) પૂર્ણ શેષ સંહતિ કહેવાય છે; દા.ત., 3 માટેની કેટલીક પૂર્ણ શેષ સંહતિઓ {0, 1, 2}, {6, 10, 5}, {4, 1, 3} છે. જો {x1, x2, …, xm} m માટેની પૂર્ણ શેષ સંહતિ હોય, (a, m) = 1 હોય તથા b કોઈ પણ પૂર્ણાંક હોય તો ગણ {ax1 + b, ax2 + b, … , axm + b} પણ m માટેની પૂર્ણ શેષ સંહતિ હોય છે.
જો a અને b m માટેના એક જ સામ્યવર્ગમાં હોય તો (a, m) = (b, m) એમ સાબિત કરી શકાય. જે સામ્યવર્ગોમાંના સભ્યો a માટે (a, m) = 1 હોય તે વર્ગોમાંથી જ એક પ્રતિનિધિ પૂર્ણાંક લઈને જે ગણ બને તેને m માટેની સંક્ષિપ્ત શેષ સંહતિ કહેવાય. m = 3 માટે જે બે સામ્ય ગણોમાંના દરેક પૂર્ણાંક માટે (a, 3) = 1 છે તે વર્ગો
{…., 5, 2, 1, 4, 7, 10, …} અને {…, 4, 1, 2, 5, 8, 11, …} છે. આમ m = 3 માટે કેટલીક સંક્ષિપ્ત શેષ સંહતિઓ {2, 5}, {1, 2}, {8, 10} છે.
m માટેની પ્રત્યેક સંક્ષિપ્ત શેષ સંહતિમાં f (m) સભ્યો હોય છે. અહીં f ઑઇલરનું વિધેય છે અને f (m) તે mથી વધુ નહિ અને m સાથે જેમનો ગુરુતમ સામાન્ય અવયવ (ગુ.સા.અ.) 1 હોય તેવા ધન પૂર્ણાંકોની સંખ્યા છે.
જો {x1, x2, …, xk} m માટેની સંક્ષિપ્ત શેષ સંહતિ હોય
(k = f(m)) અને જો (a, m) = 1 હોય તો {ax1, ax2, …., axk} પણ m માટેની સંક્ષિપ્ત શેષ સંહતિ થાય.
જો {x1, x2, …, xm} તથા {y1, y2, …, ym} m માટેની બે પૂર્ણ શેષ સંહતિઓ હોય તો દરેક xi એક અને માત્ર એક yj સાથે, m માટે સમશેષ હોય છે અને દરેક yk એક અને માત્ર xt સાથે સમશેષ હોય છે; દા.ત., {6, 10, 5} અને {4, 1, 3} એ m = 3 માટેની પૂર્ણ શેષ સંહતિઓ છે, તો 6 દ્ર 3, 10 દ્ર 4 તથા 5 દ્ર 1. આવું જ બે સંક્ષિપ્ત શેષ સંહતિઓ માટે પણ સાચું છે.
સુરેખ સમશેષતાનો ઉકેલ : પૂર્ણાંકો a, b, m તથા અજ્ઞાત પૂર્ણાંક x માટે સુરેખ સમશેષતા
ax + b દ્ર 0 (mod m)
નો ઉકેલ હોવા માટેની આવશ્યક અને પર્યાપ્ત શરત એ છે કે (a, m) bનો અવયવ હોવો જોઈએ. જો (a, m) bનો અવયવ હોય તો ઉપરની સમશેષતાને પ્રત્યેક પૂર્ણ શેષ સંહતિમાં (a, m) ઉકેલો હોય.
યુગપત્ સુરેખ સમશેષતાઓ માટે ચીની શેષ પ્રમેય (Chinese Remainder Theorem) જાણીતું છે. તદનુસાર ધારો કે યુગપત્ સમશેષતાઓ x દ્ર ai (mod mi) i = 1, 2, …, r આપેલી છે. જો m1, …, mrમાંની પ્રત્યેક જોડનો ગુરુતમ સામાન્ય અવયવ (ગુ.સા.અ.) 1 હોય તો આ યુગપત્ સમશેષતાઓનો ઉકેલ મળે. જો M = m1 m2 … mr હોય તથા જો x = bi તે સમશેષતા x દ્ર 1 (mod mi)નો ઉકેલ હોય તો યુગપત્ સમશેષતાઓનો ઉકેલ
x = a1b1 + a2b2 + … + arbr
છે. M માટેની દરેક પૂર્ણ શેષ સંહતિમાં એક ઉકેલ મળે.
સમશેષતા સંખ્યાઓના ગુણધર્મોમાં ખૂબ મહત્ત્વનો ભાગ ભજવે છે; દા. ત., સંખ્યા 2000002 પૂર્ણવર્ગ નથી એમ કોઈ પણ ગણતરી વગર કહી શકાય, કારણ આ સંખ્યાને 4 વડે ભાગતાં શેષ 2 વધે છે તે સ્પષ્ટ છે; પરંતુ કોઈ પણ પૂર્ણવર્ગ સંખ્યા 4 માટે 2 સાથે સમશેષ નથી હોતી.
ઘણા લોકોને વિભાજકતાની કસોટીમાં રસ હોય છે; દા. ત., સંખ્યાના સરવાળાને 3 વડે નિ:શેષ ભાગી શકાય તો અને તો જ તે સંખ્યાને 3 વડે નિ:શેષ ભાગી શકાય તે જાણીતું છે. હવે સંખ્યાના ડાબેથી જમણે ક્રમમાં આંકડા an, an1, …, a1, a0 હોય તો તે સંખ્યા k = 10nan + 10n1an1 + … + 10a1 + a0 થાય. હવે 10 દ્ર 1 (mod 3) હોવાથી 10r દ્ર 1r = 1 થાય માટે k દ્ર an + an1 + … + a0 મળે, જે ઉપરની વિભાજકતાની કસોટી આપે છે.
7 માટેની વિભાજકતાની કસોટી આવી બનાવી શકાય. આપેલી સંખ્યામાંથી એકમનો આંકડો છેકી નાખો અને બાકીની સંખ્યામાંથી છેકેલ આંકડાની બમણી સંખ્યા બાદ કરો. બાકી રહેતી સંખ્યાને જો 7 વડે ભાગી શકાય તો અને તો જ મૂળ સંખ્યાને પણ 7 વડે નિ:શેષ ભાગી શકાય; દા.ત., જો મૂળ સંખ્યા 8778 તો એકમનો 8 છેકતાં 877 રહે એમાંથી 8 ત્ 2 = 16 બાદ કરતાં 861 રહે. આ સંખ્યા પર પણ એ જ કસોટી લાગુ કરતાં 86 2 = 84 મળે. 84ને 7 વડે નિ:શેષ ભાગી શકાય, તેથી મૂળ સંખ્યા 8778ને પણ 7 વડે નિ:શેષ ભાગી શકાય.
જો મૂળ સંખ્યામાં એકમનો આંકડો b હોય અને તે છેકી નાખતાં રહેતી સંખ્યા a હોય તો મૂળ સંખ્યા 10a + b થાય. હવે 10a + b દ્ર 0 (7) તો 20a + 2b દ્ર 0 અને તેથી 20a + 2b દ્ર 21a અથવા a 2b દ્ર 0 થાય. આથી ઊલટું પણ સાચું છે.
આવી કસોટી 13 માટે બનાવવા માટે એ નોંધી શકાય કે 10a + b દ્ર 0 (mod 13) તો 40a + 4b દ્ર 0 (13), તેથી 40a 39a + 4b દ્ર 0, જેથી a + 4b દ્ર 0. આમ એકમના આંકડાને છેકી; બાકીની સંખ્યામાં તેના ચાર ગણા ઉમેરવામાં આવે. જો એ રીતે મળતી સંખ્યાને 13 વડે નિ:શેષ ભાગી શકાય તો અને તો જ મૂળ સંખ્યાને પણ 13 વડે નિ:શેષ ભાગી શકાય.
આ રીતે કોઈ પણ અવિભાજ્ય માટે વિભાજકતાની કસોટી બનાવી શકાય.
અરુણ મ. વૈદ્ય