[Maths boy]

hey, im just wondering if anyone can help me with this 1st year maths problem in the number and structure unit.

a) Using the Euclidean algorithm find the highest common factor of 1905623 and 2766853. Find also two integers h and k such that 1905623h + 2766853k = the HCF you have found.

b) Invent a linear congruence problem of the form with your own choice of c where c >1500. Find two different solutions to your problem i.e. find two different pairs of values for x and y.

c) Invent a different linear congruence problem with 1905623 and 2766853 which does not have any solutions (i.e. with a different value of c.) Explain why it does not have any solutions.

[sophiiexx]

2766853 = 1905623x1 + 861320
1905623 = 861320x2 + 182983
861320 = 182983x4 + 129388
182983 = 129388x1 + 53595
129388 = 53595x2 + 22198
53595 = 22198x2 + 9199
22198 = 9199x2 + 3800
9199 = 3800x2 + 1599
3800 = 1599x2 + 602
1599 = 602x2 + 395
602 = 395x1 + 207
395 = 207x1 + 188
207 = 188x1 + 19
188 = 19x9 +17
19 = 17x1 +2
17 = 2x8 + 1
2 = 1x2 + 0
Therefore the highest common factor is 1. Rearrange these equations and substitute values in to find h and k for
1905623h + 2766853k = 1

[BabyMaths]

Sophie, we're not supposed to post full solutions.

By the way you seem to have gone wrong.

You can check here

http://www.calculatorsoup.com/calcul...-algorithm.php

or at wolframalpha.

[BabyMaths]

Duplicate thread. Original is here: http://www.thestudentroom.co.uk/show....php?t=2035118

[sophiiexx]

(Original post by BabyMaths)
Sophie, we're not supposed to post full solutions.

By the way you seem to have gone wrong.

You can check here

http://www.calculatorsoup.com/calcul...-algorithm.php

or at wolframalpha.

Damn it, i wrote the 3 and 2 the wrong way round in the remainder to the first equation, that's how you do it though.