Question

for natural numbers p and a, if p doesn't divide a, then p and a are coprime, is that right?

Answer 1

go to this link - http://nrich.maths.org/4352

Answer 2

Take the numbers p=6, a=3. Then p does not divide a, but they aren't coprime.

Answer 3

is that the same as relatively prime?

Answer 4

Damn! Thanks KingGeorge. I was going over my work last night, and realised that my assertion they must be coprime didn't quite convince me as much as earlier...

Answer 5

If p is prime however, your assertion is true.

Answer 6

p is prime. Maybe I was right after all ... I just can't remember why I said that. *brain melt*

Answer 7

Oh right I see why it's true. Fairly trivial. a has a prime factorisation which doesn't include the prime p, since otherwise p would divide a. Therefore a and p share no common prime factors, so the greatest common divisor of both is 1, so they're coprime... I knew there was a reason...

Answer 8

exactly. If you don't mind my asking, but what was the larger problem where you used this fact?

Answer 9

I am trying to prove a fact that Euler believed to be true in 1732 but couldn't prove. He believed that if p is a prime, p doesn't divide a, and p doesn't divide b (a and b are natural numbers), then this implies that p divides (a^(p-1) - b^(p-1)). I am fairly sure I have proven it, I'm just going over my work to make sure it makes sense. I used Fermat's Little theorem, which I find interesting, given that Euler had access to that theorem in his day. But perhaps we have extra tools Euler didn't have?

Answer 10

Odd. Using Fermat's Little Theorem and some properties of divisibility, it's pretty obvious that that's true.

Answer 11

That's what I thought! So I had to be sure my reasoning is correct and I hadn't just deluded myself. A tribute to advances in notation I think.

Answer 12

Probably. It might be because we have a much more formal definition of "modulo." I'm still surprised Euler couldn't formulate a proof though.