1. ## Gcd question

g.c.d.(r,s)

2. See that s is irreducible.

3. Originally Posted by vincisonfire
See that s is irreducible.
Thanx but still dont kno how to show gcd (r,s)=1

4. Because s in irreducible, gcd(r,s) is either s or 1. Show that s doesn't divides r (just long division or factorization of r).

5. Originally Posted by vincisonfire
Because s in irreducible, gcd(r,s) is either s or 1. Show that s doesn't divides r (just long division or factorization of r).
Thanx that makes sense now. i will try it out

6. The original poster asked to prove $\displaystyle \gcd( r,s ) = 1$ as integers not as polynomials.
If it was polynomials then the result works since $\displaystyle x^4+x^3+x^2+x+1$.

Consider $\displaystyle f=x+1$ and $\displaystyle g=(x+3)^2$ then $\displaystyle \gcd (f(x),g(x))=1$.
However if $\displaystyle x=1$ then $\displaystyle f(1) = 2$ and $\displaystyle g(1) = 16$ but $\displaystyle \gcd( f(1), g(1)) \not = 1$.
----

To solve this problem we need to know a theorem:
Let $\displaystyle a,n,m>0$ then $\displaystyle \gcd( a^n -1, a^m - 1) = a^d - 1$ where $\displaystyle d=\gcd(n,m)$.

This means, $\displaystyle \gcd( m^5 - 1, m^{16} - 1) = m - 1$ since $\displaystyle \gcd(5,16)=1$.
But then, $\displaystyle \gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1$.
This completes the proof since $\displaystyle \tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4$ and $\displaystyle \tfrac{m^{16}-1}{m-1} = 1 + m + ... + m^{15}$.

7. Originally Posted by ThePerfectHacker
The original poster asked to prove $\displaystyle \gcd( r,s ) = 1$ as integers not as polynomials.
If it was polynomials then the result works since $\displaystyle x^4+x^3+x^2+x+1$.

Consider $\displaystyle f=x+1$ and $\displaystyle g=(x+3)^2$ then $\displaystyle \gcd (f(x),g(x))=1$.
However if $\displaystyle x=1$ then $\displaystyle f(1) = 2$ and $\displaystyle g(1) = 16$ but $\displaystyle \gcd( f(1), g(1)) \not = 1$.
----

To solve this problem we need to know a theorem:
Let $\displaystyle a,n,m>0$ then $\displaystyle \gcd( a^n -1, a^m - 1) = a^d - 1$ where $\displaystyle d=\gcd(n,m)$.

This means, $\displaystyle \gcd( m^5 - 1, m^{16} - 1) = m - 1$ since $\displaystyle \gcd(5,16)=1$.
But then, $\displaystyle \gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1$.
This completes the proof since $\displaystyle \tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4$ and $\displaystyle \tfrac{m^{16}-1}{m-1} = 1 + m + ... + m^{15}$.
I havent come across this theorem, would i be able to do it some other way?

8. Originally Posted by maths900
I havent come across this theorem, would i be able to do it some other way?
You can find the proof here.