PDA

View Full Version : Linear Congruence



DATA
04-13-2002, 06:03 PM
LINEAR congruence

hi,

To solve 25 x(congruent)*5 (mod *20)

d=(25,*20)=5, d|*5 the congruence has exactly 5 solutions modulo *20.

We know if (a,m)=d and d|b,the linear congruence

ax(congruent)b (mod m) has exactly d solution modulo m,given by
t,t+(m/d),t+2(m/d),...t+(d-*)m/d,where t is the solution ,unique modulo m/d,of the linear congruence

(a/d)x(congruent)b/d(mod(m/d))

Solution y =t +(km)/d for some k.

To solve 25 x(congruent)*5 (mod *20)

it has 5 solutions modulo *20

To find them we divide by 5 and solve the congruence
5x(congruent)*(mod 24)
we use y=t +(km)/d

for(k=0,*,2,*,4) m/d is calculated

i.e y=t+(k*24) for k=0,*,2,*,4

How ever how is t actually computed and the 5 solutions actually found?

regards Data.