Thread: prove fraction is irreducible

Prove that the fraction n/(3n+1) is irreducible for any n of N.
Thank you!

Essentially, you need to show that n and 3n+1 will never have a common factor (other than "1", of course). You might try a "proof by contradiction". If they had a factor in common, if n= ax and 3n+1= ay, what happens if you replace the "n" in ay= 3n+1 by ax? Remember that a, x, and y are all integers.

ok, lets say n=ax and 3n+1=ay =>
3ax+1=ay => a(3x+1/a)=ay => 3x+1/a=y...but we know that Y is an integer so it can not be
Wow, thanks a lot! This was itching my brain for a couple of days now...guess I missed the spark...my first attempt was induction, but I had no ideea what to get out of it...
Thanks again!

Originally Posted by TheYesMen

ok, lets say n=ax and 3n+1=ay =>
3ax+1=ay => a(3x+1/a)=ay => 3x+1/a=y...but we know that Y is an integer so it can not be
Wow, thanks a lot! This was itching my brain for a couple of days now...guess I missed the spark...my first attempt was induction, but I had no ideea what to get out of it...
Thanks again!

Slightly different way of looking at: if 3ax+ 1= ay then ay- 3ax= a(y- 3x)= 1 and a and y- 3x are integers.