Thread: Highest Common Factor using Euclidean Algorithm

SOLVED, THANKS!


Hi,

Supposedly by remainder theorem that
a=a' mod n
and
a+b = a'+b' mod n
and possibly
a.b = a' . b' mod n

I need to calculate the remainder when
4901^10 + 3^5 is divided by 7

As I had to prove the above formulae, I am sure I have to use them however I dont have much of an idea to actually use them.



BELOW IS SORTED

I am having problems finding the highest common factor using the Euclidean Algorithm and then representing hcf(a,b)=x.a+y.b

I have been able to calculate hcf(483,315) to find that the highest common factor is 21 and represented it as 21=2.483-3.315


However I have come across a problem when trying to calculate hcf(882,112) as from the first iteration I get:
882=112.6+210
The remainder is bigger than the multiplier, thus preventing me from carrying on?


Also I have had a problem calculating the representation of hcf(493,103). I have calculated the highest common factor to be 1 but when I work out the representation I get 1=2.493-7.103 which is clearly wrong.

I can post any additional working if required.

Thank you very much in advance for any help or tips.

Hello, BlueEagle!

Don't kick yourself too hard . . .

I have come across a problem when trying to calculate HCF(882,112).

From the first iteration I get: .
The remainder is bigger than the multiplier. . . . . Of course it is!

112 goes into 882 seven times . . .

Ha ha yeah, just figured, I deleted my previous reply to solving the previous question and was just about to delete the topic.
How foolish of me lol!
Thank you very much for helping out though!

I would like to ask another question here if possible:

Supposedly by remainder theorem that
a=a' mod n
and
a+b = a'+b' mod n
and possibly
a.b = a' . b' mod n

I need to calculate the remainder when
4901^10 + 3^5 is divided by 7

As I had to prove the above formulae, I am sure I have to use them however I dont have much of an idea to actually use them.

The last 3 digits of is 244.

What is the reaminder when it is divided by 7?. That's your answer.

I solved it a different way:
a=b mod n
a^m=b^m mod n

Therefore
4901 = 1 mod 7
4901^10 = 1^10 mod 74901^10 = 1 mod 7

3=3 mod 7
3^5=5 mod 7

Adding the remainder is 6!

Thanks for the advice though!