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 $\gcd( r,s ) = 1$ as integers not as polynomials.
If it was polynomials then the result works since $x^4+x^3+x^2+x+1$.

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

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

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

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

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

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

This means, $\gcd( m^5 - 1, m^{16} - 1) = m - 1$ since $\gcd(5,16)=1$.
But then, $\gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1$.
This completes the proof since $\tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4$ and $\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.