Quote:

Originally Posted by

**Cabouli** 1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

gcd(a,b)=1 then ax+by=1

gcd(a,c)=1 then ax+cy=1

let gcd(a,bc)=d then ax+bcy=d

I cannot see how to proceed

So we have: $\displaystyle \gcd(a,b) = 1 \ \Rightarrow \ ax + by = 1$

Multiply both sides by $\displaystyle c$ to get: $\displaystyle acx + bcy = c$

Now, since $\displaystyle \gcd(a,b) \mid acx$ and $\displaystyle \gcd(a,b) \mid bcy$, then $\displaystyle \gcd(a,b) \mid c$ (Why?).

Thus, $\displaystyle \gcd (a,b)$ is a divisor of both $\displaystyle a$ and $\displaystyle c$. What can you conclude?

Quote:

2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

gcd(a,b)=1 ax+by=1

c|a therefore a=cm ,m an integer

therefore cmx+by=1

so c(mx)+by=1

therefore gcd(c,b)=1

Does this work?

Sure does.

Quote:

3. Prove that if a is odd, then 24|a(a^2-1)

sufficient to show RHS is divisible by 3, 2 and 4

let a=2k+1 since it is odd

a(a^2-1)=2k(2k+1)(2k+2)

this is clearly divisible by 2, 3 and 4

Is that idea sufficient?

(Yes) Although you would probably want to say more as to why it is 'clear' that this is the case.

Quote:

4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

gcd(a,b)=1 and ax+by=1

let gcd(a+b,a-b)=d so (a+b)x+(a-b)y=d so d|(a+b) and d|(a-b)

I can see I need d|2a and d|2b but can't see how to get there

Suppose $\displaystyle p \mid (a+b)$ and $\displaystyle p \mid (a-b)$ where $\displaystyle p$ is prime. This means that: $\displaystyle p \mid (a+b + (a-b) \Leftrightarrow p \mid 2a$. Similarly, we get $\displaystyle p \mid 2b$.

Can you finish off?

Quote:

5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

gcd(a,b)=1 and ax+by=1

let gcd(a^n,b^n)=d so a^nx+b^ny=d and a^n=md b^n=pd

again don't know where to proceed

Suppose $\displaystyle \gcd (a^n, b^n) > 1$. This means that there exists a prime $\displaystyle p$ such that $\displaystyle p \mid a^n$ and $\displaystyle p \mid b^n$. Can you arrive at a contradiction? (Remember, if $\displaystyle p \mid mn$, then either $\displaystyle p \mid m$ or $\displaystyle p \mid n$)

Quote:

6. Prove that lcm(a,b)xgcd(a,b)=ab

If a=mnp.. m,n,p,... are prime and b=efg.. e,f,g,... are prime

then lcm(a,b)=mnp...efg... assuming none of mnp... and efg... are common

If any are common they will not be in the lcm(a,b)

gcm(a,b)= common elements from mnp.... and efg.... if none then gcm(a,b)=1

aXb=mnp...efg...

gcd(a,b)Xlcm(a,b)=mnp...efg... from above

I think I have the right idea but a messy approach to showing it.

Can't quite read what you have there but I'm guessing you're going down the prime factorization approach.

So, let $\displaystyle a = p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ and $\displaystyle b = p_1^{f_1}p_2^{f_2}\cdots p_n^{f_n}$ where $\displaystyle e_j, f_j$ may equal to 0.

By definition, we have: $\displaystyle \gcd (a,b) = p_1^{\min (e_1, f_1)}p_2^{\min (e_2, f_2)}\cdots p_n^{\min (e_n, f_n)}$

and: $\displaystyle \text{lcm} (a,b) = p_1^{\max (e_1, f_1)}p_2^{\max (e_2, f_2)}\cdots p_n^{\max (e_n, f_n)}$

Multiply them both together and it should be clear from there.