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.
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!
It looks confusing to me... though it looks correct ^^
------------------------------
Known fact : d is a common divisor of a and b.
We want to prove $\displaystyle \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 $\displaystyle A \Rightarrow B ~:~ (a,b)=d \Rightarrow (x,y)=1$
It corresponds to what you've written here :
The thing is that it's not very good to sa "it's that because if it was not..."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...
What you've done is sort of proving the contrapositive.
Suppose $\displaystyle (x,y)=s > 1$. Then $\displaystyle (a,b)=(dx,dy)=d(x,y)=ds \neq d$
So we have proved that $\displaystyle \color{red} \overline B \Rightarrow \overline A$, which is equivalent to $\displaystyle 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 $\displaystyle A \Leftarrow B ~:~ (a,b)=d \Leftarrow (x,y)=1$
If $\displaystyle (x,y)=1$, then $\displaystyle (dx,dy)=d$... The rest follows
We want to prove $\displaystyle p \nmid a \implies (a,p)=1$
And we are going to prove the contrapositive (equivalent to the initial implication), that is to say :
$\displaystyle (a,p) \neq 1 \implies p \mid a$
-------------------------
$\displaystyle (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 $\displaystyle d > 1$, so it cannot be 1.
Thus $\displaystyle d=p$.
--> $\displaystyle p \text{ divides } a \quad \text{Q.E.D.}$