Expert: Sherry Wallin - 1/16/2009

Question
QUESTION: Hello, I signed up for abstract algebra this semester but I did not do proofs in a long time so I need some help.

I need to prove that 2^n*3^2n - 1 is always divisible by 17, I understand that I must use induction but I get lost.  Can you walk me through it? thank you!

ANSWER: Hi Bohdan~
   Sure I'd be happy to help you. You always want to establish the 'base' case, usually n = 0 or 1. By the way 0 works but we'll begin with n = 1: 2^1*3^(2*1)-1 = 2*3^2-1 = 2*9-1 = 17 and 17|17 because 17(1) = 17 so it is true for n=1
Next (this is the induction step) assume it is true for n=k, i.e.
assume 2^k*3^(2*k)-1.This means that 17 divides 2^k*3^(2*k)-1, which int turn symbolically is 17|2^k*3^(2*k)-1 or 2^k*3^(2*k)-1 = 17m, m some integer. This is equivalent to 2^k*3^(2k)= 17m+1 The next step is to try to show through some type of algebraic manipulation that it is true for n = k+1, so show it is true 2^(k+1)*3^(2(k+1))-1. Note this is equal to 2^k*2*3^[2(k+2)]-1 which is equal to 2^k*2*3^(2k)*3^2-1 and we can change the order of multiplication:  2^k*3^(2k)*2*3^2-1. Now this is where you want to use the induction step. Substitute the case of n = k into the case n = k+1:

**I put curly braces around the part I want to substitute for...
{17m + 1}*2*3^2-1  = {17m+1}*2*3^2-1 = {17m+1}*2*9-1 ={17m + 1}18-1
= 17m*18 + 18 -1 = 17m*18+17 = 17(18m+1) = 17r  for some integer r. or equivalently 17|{17m + 1}*2*3^2-1 , therefore by induction
2^n*3^2n - 1 is always divisible by 17  for any n in the natural numbers.

I hope this is clearly explained and understandable for you.

Math Prof

---------- FOLLOW-UP ----------

QUESTION: Oh my gosh thank you for your help! I will hit the books soon, I actually figured it out before I checked your anser but thank a million!

I have another question, this one I think I won't get for quite some time:

let a and b be positive integers, and let d = gcd(a,b) and m = lcm(a,b). If t divides both a and b, prove that t divides d. If s is a multiple of both a and b, prove that s is a multiple of m.

thanks a million  

Answer
Hi Bohdan~ Let's take one step at a time...if gcd(a,b) = d then d can be written as a linear combination of a and b. Let's say d=ax+by. If t divides both a and b then there exists an e in the integers such that
a = et and there exists an f in the integers such that b = ft. Now substitute those values into d = ax +by getting etx + fty = d or
t(ex+fy) = d which implies t divides d by the definition of divides.

I hope this helps you get going. Think about the rest.

Math Prof