







CTK Exchange
Monty
Member since Jul2704

May1207, 10:25 PM (EST) 

"Modular arithmetic"

The definition of mod is, I understand, if a = b mod n, then (ab) is divisible by n, or ab=kn, with k an integer I'm applying this to Fermat's little theorem: so if a^(p1) = 1 mod p, then a^(p1)1 = kp multiplying both sides by a, we get a^p  a = kap = cp So a^p  a = cp and a^(p1)1 = kp would seem to be equivalent. HOWEVER, they seem NOT equivalent if a=p a=p=2, 2^22=2=1*2, but 2^11=1 not a product of 2 a=p=3, 3^33=273=24=8*3, but 3^21=91=8 not a product of 3 Why is this? It would seem that I'm somehow dividing by ap, which is of course NG if a=p. But I don't see where.... ??? Monty 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



Monty
guest

May1507, 12:29 PM (EST) 

2. "RE: Modular arithmetic"
In response to message #1

I see what you're saying, but still don't understand. From the definition of mod I got an equation which said a^(p1)1=kp, that is it equals a product of p. I then multiplied by a and got a^pa=cp, so it's also a product of p. If a=0 (mod p), then a=fp  a is a product of p. So my second equation is fp^pfp=cp. Let's see, I can factor out p, so I get fp^(p1)f=c. Now the function y=x^(x1)+k is a little irregular (when x is negative....), but otherwise it's an ok function. So I'm still missing the point. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




alexb
Charter Member
2009 posts 
May1507, 12:39 PM (EST) 

3. "RE: Modular arithmetic"
In response to message #2

>I see what you're saying, but still don't understand. From >the definition of mod I got an equation which said >a^(p1)1=kp, This is only true if a is coprime with p. >I then >multiplied by a and got a^pa=cp, This is true for any a, for if pa the fact is trivial. >so it's also a product of p. If a=0 (mod p), then a=fp  a is a product of p. So my >second equation is fp^pfp=cp. This is trivially true, yes. >Let's see, I can factor out >p, so I get fp^(p1)f=c. Now the function y=x^(x1)+k is a >little irregular (when x is negative....), but otherwise >it's an ok function. > >So I'm still missing the point. I am not sure what point it is, so I am going to check your original message.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



alexb
Charter Member
2009 posts 
May1507, 12:42 PM (EST) 

4. "RE: Modular arithmetic"
In response to message #0

>The definition of mod is, I understand, > if a = b mod n, then (ab) is divisible by n, or ab=kn, >with k an integer > I'm applying this to Fermat's little theorem: > so if a^(p1) = 1 mod p, then a^(p1)1 = kp > multiplying both sides by a, we get > a^p  a = kap = cp >So a^p  a = cp and a^(p1)1 = kp would seem to be >equivalent. In a sense, yes, but you must be cautious as to the meaning of equivalence. a^(p1)1 = kp holds only for a coprime with p, whereas a^p  a = cp holds for any a, 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 19962018 Alexander Bogomolny

