Ariel Pacetti on Tue, 16 Sep 2003 23:54:12 -0500 (CDT)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: gcd of Modded integers


No because the congruence equations are equivalence clase. Look at this:
 since (9,26)=1, there is an element in the same equivalence class as 9
but not divisible by 3 (for example 35 = 9 + 26). Then 3 is not a divisor
of the equivalence class.
A congruence number (i.e. a number Mod(a,b)) will have a non-trivial
divisor if and only if the gcd(a,b) is different from 1.
For example:

gcd(Mod(3,18),Mod(9,18))= Mod(3,18)

Ariel


On Tue, 16 Sep 2003, Manish wrote:

> I came across this on my GP/PARI Version 2.1.5.
>
> shouldnt I expect   gcd to be Mod(3,26)
>
>
> ? gcd(Mod(9,26), Mod(3,26))
> %1 = Mod(1, 26)
>
>
> thanks
> Manish
>