Highest Common Factor using Euclidean Algorithm
Supposedly by remainder theorem that
a=a' mod n
a+b = a'+b' mod n
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:
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.