[kexy]

I'm just trying to work my way through some questions for my Number Theory revision and there's a few things I haven't quite understood properly from the very beginning of the course.

I'm sure they're all really simple stuff i'm just unsure where to start...
If someone could point me in the right direction by telling me what the question is actually asking for and an idea of the effort then i'd be really really grateful!

Find the complete set of residues modulo 8 such that every element is (a) Even, (b) Odd and (c) Prime.
I don't even know what a complete set of residues is - I can't find anything about it that doesn't confuse me, does anyone know a nice simple definition I can try and work from?

Solve if possible the following congruence equation:

20x42 mod50

I think I know how to solve this... but I can only think of by trying every single x up to 50 one by one and checking if it fits. Is there a quick way?

Rewrite the following linear congurence as a system of linear congruences and solve.
24x 22 mod 442

What does it mean to rewrite it? Is there are general method and how do i then solve the congruence?

[Simba]

Well, the residues modulo 8 are {0, 1, 2, 3, 4, 5, 6, 7}. So the complete residue class such that every element is even would be {0, 2, 4, 6} I presume. It's a bizarre question!

If 20x = 42 mod 50, we don't have any solutions, are you sure you typed it right?

For 24x = 22 mod 442, split 442 up into its prime factors then use the Chinese remainder theorem/inspection appropriately . You might want to cleverly reduce 442 first (think of a common factor of the terms).

Hope this helps!

[kexy]

Originally Posted by Simba

Well, the residues modulo 8 are {0, 1, 2, 3, 4, 5, 6, 7}. So the complete residue class such that every element is even would be {0, 2, 4, 6} I presume. It's a bizarre question!

If 20x = 42 mod 50, we don't have any solutions, are you sure you typed it right?

For 24x = 22 mod 442, split 442 up into its prime factors then use the Chinese remainder theorem/inspection appropriately . You might want to cleverly reduce 442 first (think of a common factor of the terms).

Hope this helps!

First Question

I've read further into my notes and I think my first question is supposed to be a non trivial example - I have second one which is exactly the same but for modulo 9.

So this time I can have {1, 2, 3, 4, 5, 6, 7, 8, 9} incedently - does it start at 0 and go to 8 or start at 1 and go to 9?

My idea only works for the latter.

I only want the evens so take {2, 4, 6, 8} but I can see that 10=1 mod9 , 12=3 mod9, 14=5 mod9, 16= 7 mod9 & 18= 9 mod9, so can I say the residue set is {2, 4, 6, 8, 12, 14, 16, 18}?

Question 2
It's actually solve 19 42 mod 50. Sorry!

How do you solve one anyway?

[wellison999]

Originally Posted by kexy

Question 2
It's actually solve 19 42 mod 50. Sorry!

How do you solve one anyway?

Firstly, observe that hcf(19,50)=1, so a solution must exist (and there will be just one).

To find the solution, simply use Euclid's algorithm - we can get 19a + 50b = 1 for some a and b, and then just multiply through by 42 to get our answer, which will be 42a (mod 50).

[kexy]

Originally Posted by wellison999

Firstly, observe that hcf(19,50)=1, so a solution must exist (and there will be just one).

To find the solution, simply use Euclid's algorithm - we can get 19a + 50b = 1 for some a and b, and then just multiply through by 42 to get our answer, which will be 42a (mod 50).

Is the number of solutions linked to the HCF then - if I had an HCF of 12 for something do i then have 12 solutions to find?

How does this euclid's algorithm work. The wikipedia article is very confusing. If i'm solving 19a +50b =1 do I break down 50 and 19 into common factors or something?

[Calira]

Euclid's algorithm works on the fact that, if a>b, then
gcd(a,b) = gcd(a-b,b)
so
gcd(50,19) = gcd(31,19) = gcd(19,12) = gcd(12,7) = gcd(7,5) etc.

I can't remember the proof of gcd(a,b)=gcd(a-b,b) offhand, but from what I remember, it's not too hard to understand if you read it.

You can speed it up with large numbers, eg.
gcd(53675,1464)
If you see that 1464 goes into 53675 just over 36 times, you can jump to
gcd(53675,1464 = gcd(53675-(1464*36),1464) to cut down on repeated subtraction.

If you're solving 50a + 19b = 1, you can work directly from the steps of Euclid's algorithm.

50 - 2*19 = 12, so 50*1 + 19*(-2) = 12
19 - 12 = 7, so 19 - ((50*1) + 19*(-2)) = 7 <---- which can simplify to 50*(-1) + 19*3 = 7
Then do 12-7, then 7-5, and keep working until you get down to expressing 1 in multiples of 50 and 19.

Hope I explained that clearly enough

[joth]

You're also correct for the first bit. A reduced set of representatives for mod k means picking an element from each of the k equivalence classes; in other words, a set of k numbers such that reducing them all down mod k gives you {1, 2,....., k}

Doing mod 5 as an example:
Even: {0, 2, 4, 6, 8}
Odd: {1, 3, 5, 7, 9}
Prime: {2, 3, 5, 11, 19}