hello can someone please help me to solve this problem:
2008 mod 71,
92 mod 41,
342 mod 71
b)determine all a and b that verify
a2 mod 41=40
b2 mod 71=20
this is my answer:
a) 2008 mod 41=40
2008 mod 71=20
92 mod 41=40
342 mod 71=20
b) i noticed that a=9 is a solution for : a2 mod 41=40
and b=34 is a solution for : b2 mod 71=20
but the problem require finding all the solution .can some one please help me .
As an example, here's the way I would do it: Suppose we want all solutions a
2 = 71 mod(73). First we find a solution. Well I didn't pick that out of thin air so I know 12
2 is a solution so lets look at
(12 + m)
2 = 71 mod(73)
That just means
12
2 + 24 m + m
2 = 71 + 73 n
and since 12
2 = 71 mod(73), we can absorb the 12
2 and 71 into the n. That is
24m + m
2 = 71 - 12
2 +73n = 71 - 144 +73n = -73 + 73n = 73(n-1)
to get
24m + m
2 = (24 + m) m = 73 j
If we let (24+m) be some multiple of 73 we have
24 + m = 73 k
or
m = 73 k - 24 = 73 (k-1) + 49 = 73 r + 49
Note that for r=-1, we get 12 + m = -12 and that (-12)
2 is the same as 12
2. We have
\(\displaystyle a^2 = (12\, +\, 73\, r\, +\, 49)^2\, = (61\, +\, 73\, r)^2\)
or
\(\displaystyle a = \pm\, (61\, mod(73))\)
Is that the only solutions? Well, you might be able to convince yourself of that if you considered (a+d)
2 where
\(\displaystyle a +d \ne \pm\, (61\, mod(73))\)
BTW:\(\displaystyle a = - (61\, mod(73))\) just means a=-(61 + 73 n) or a=-61-73n= 12-73-73n = 12+73(1-n) or a=12mod(73). Simularly a=61mod(73) is he same as a=-12mod(73). Putting that altogether we have
\(\displaystyle a = \pm\, 12\, mod(73)\)
