My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
January 20th, 2018, 07:20 AM   #1
Member
 
Joined: Sep 2011

Posts: 83
Thanks: 1

Mathematical induction in Number Theory

I have encountered difficulties in solving this question. Your help is greatly appreciated!
Attached Images
File Type: jpg 1.jpg (14.8 KB, 21 views)
Alexis87 is offline  
 
January 20th, 2018, 07:23 AM   #2
Senior Member
 
Joined: Oct 2009

Posts: 232
Thanks: 84

Let's take $n=2$ for the moment. Assume $(a,b^2) = d \neq 1$. What do you know then by definition of the gcd?
Micrm@ss is offline  
January 20th, 2018, 07:47 AM   #3
Member
 
Joined: Sep 2011

Posts: 83
Thanks: 1

GCD is the greatest common divisor, d of both a and b where a/d and b/d.

May I ask why use that assumption of not equal to 1? How would you continue from there?
Alexis87 is offline  
January 20th, 2018, 09:33 AM   #4
Senior Member
 
Joined: Oct 2009

Posts: 232
Thanks: 84

Quote:
Originally Posted by Alexis87 View Post
GCD is the greatest common divisor, d of both a and b where a/d and b/d.

May I ask why use that assumption of not equal to 1? How would you continue from there?
Because I'm suggesting you to do a proof by contradiction/contrapositive.
Micrm@ss is offline  
January 20th, 2018, 03:41 PM   #5
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 276
Thanks: 141

Math Focus: Dynamical systems, analytic function theory, numerics
Induction does not seem (to me) to be a very natural way to approach this proof. That isn't to say that it can't be done via induction. Here is a sketch.

(1) First prove the following claim:
Suppose $(a,b) = 1$ and $(a,c) = 1$, then $(a,bc) = 1$.

(2) Now, fix $a,b$ and assume $(a,b) = 1$. Take $n=1$ for the base case which is complete by assumption.

(3) Assume inductively that $(a,b^n) = 1 $ holds for some $n \in \mathbb{N}$. Now, set $c = b^n$ so that $(a,b) = (a,c) = 1$ holds and apply the claim from (1). This proves by induction that $(a,b^{n+1}) = 1$ for every $n \in \mathbb{N}$.

(4) Apply a similar argument as in (3) to prove that for $n\in \mathbb{N}$ fixed, $(a^m,b^n) = 1$ for every $m \in \mathbb{N}$ which concludes the proof.
SDK is offline  
January 27th, 2018, 08:13 AM   #6
Member
 
Joined: Sep 2011

Posts: 83
Thanks: 1

Hi SDK,

for step 4 do I write like the following? :

suppose (a,c)=1 and (p,c) =1 then (ap, c) =1
since (a , b^n) = 1 as proven earlier, assume that (a^m, b^n) = 1 holds.
Let p = a^m so that (a,c) = (ap, c) = 1 where c = b^n.
Therefore, (a^m, b^n) = 1 fpr every m, n is an element of natural numbers.
Alexis87 is offline  
January 27th, 2018, 08:14 AM   #7
Member
 
Joined: Sep 2011

Posts: 83
Thanks: 1

Hi SDK,

for step 4 do I write like the following? :

suppose (a,c)=1 and (p,c) =1 then (ap, c) =1
since (a , b^n) = 1 as proven earlier, assume that (a^m, b^n) = 1 holds.
Let p = a^m so that (a,c) = (ap, c) = 1 where c = b^n.
Therefore, (a^m, b^n) = 1 fpr every m, n is an element of natural numbers.
Alexis87 is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

Tags
induction, mathematical, number, theory



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
mathematical induction erblina zeqiri Algebra 1 January 5th, 2015 05:15 PM
Mathematical Induction. spuncerj Pre-Calculus 1 November 28th, 2014 05:43 PM
mathematical induction medos Algebra 5 October 31st, 2012 04:54 PM
Mathematical Induction MathematicallyObtuse Algebra 2 February 5th, 2011 04:59 PM
Mathematical Induction help please. firstsin Abstract Algebra 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.