# Thread: prove Euclidean Algorithm based ...

1. ## prove Euclidean Algorithm based ...

Q1) prove that if d is a positive integer, d\a and d\b, then (a,b) = d...if and only if (d\a, d\b) = 1.

Q2) Prove that if P is a prime and a is an integer, and p does not divide a then (a,p) = 1.

2. Hello,

Originally Posted by Vedicmaths
Q1) prove that if d is a positive integer, d\a and d\b, then (a,b) = d...if and only if (d\a, d\b) = 1.
These notations look weird to me...

For "d divides a", I'd say d|a or d\a.
But for $\frac da$, it's rather d/a..

Are you allowed to use Bézout's identity ?

3. yeah I am sorry...that form is d divides a and d divides b...I messed up with my signs!

I don't think so we have studied this before! I think we have to use the division algorithm for that purpose...
but I tried solving it...please approve if that makes sense or help me out!

when we say the common divisor of a and b is d it means this:
a = d * x
b = d * y
so when we divide a on d ( a/d) 'x' would remain.
in other words x = a / d
and in the same way when we divide a on d (a/d) y would remain. in other words y = b/ d
note that (x, y)= 1 because if it wasn't 1 the greatest divisor of a and b would be more than d ( for example if (x,y)= s we would have (a, b) = (dx, dy) = d*(x,y)= d*s)
so (x,y)=1
and (a/d , b/d)= ( x , y)=1...

Thanks for offering help!

4. It looks confusing to me... though it looks correct ^^

------------------------------
Known fact : d is a common divisor of a and b.

We want to prove $\underbrace{(a,b)=d}_{\color{red}A} \Leftrightarrow \underbrace{(x,y)=1}_{\color{red}B}$, where x and y are defined like you did

Proving $A \Rightarrow B ~:~ (a,b)=d \Rightarrow (x,y)=1$
It corresponds to what you've written here :
note that (x, y)= 1 because if it wasn't 1 the greatest divisor of a and b would be more than d ( for example if (x,y)= s we would have (a, b) = (dx, dy) = d*(x,y)= d*s)
so (x,y)=1
and (a/d , b/d)= ( x , y)=1...
The thing is that it's not very good to sa "it's that because if it was not..."
What you've done is sort of proving the contrapositive.

Suppose $(x,y)=s > 1$. Then $(a,b)=(dx,dy)=d(x,y)=ds \neq d$
So we have proved that $\color{red} \overline B \Rightarrow \overline A$, which is equivalent to $A \Rightarrow B$.

Yes, it looks like it's a lot, but I'm just trying to explain as much as possible the reasoning

Proving $A \Leftarrow B ~:~ (a,b)=d \Leftarrow (x,y)=1$
If $(x,y)=1$, then $(dx,dy)=d$... The rest follows

5. Originally Posted by Vedicmaths
Q2) Prove that if P is a prime and a is an integer, and p does not divide a then (a,p) = 1.
We want to prove $p \nmid a \implies (a,p)=1$

And we are going to prove the contrapositive (equivalent to the initial implication), that is to say :

$(a,p) \neq 1 \implies p \mid a$

-------------------------
$(a,p) \neq 1 \Leftrightarrow \text{ There exists d} > \text{1, such that (a,p)=d.}$

Therefore, d divides a and p.

But the only divisors of p are 1 and p itself.
We said that $d > 1$, so it cannot be 1.

Thus $d=p$.

--> $p \text{ divides } a \quad \text{Q.E.D.}$

6. thanks a lot Moo!
yeah I kinda figured it out that I have not mentioned enough about what I knew. but yeah what you have written totally makes sense and its kinda cool way to say qed!