My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
  • 1 Post By mrtwhs
Reply
 
LinkBack Thread Tools Display Modes
September 17th, 2017, 06:42 PM   #1
Newbie
 
Joined: Sep 2017
From: San Diego

Posts: 6
Thanks: 0

Why is it sufficient

In class the professor proved that the product of 2 or more integers of the form 4n + 1, is of the same form.

I understand most of the proof, but in class he said it was sufficient to prove the statement with only two integers, but I do not understand why you only need two integers to prove it. I'll give the beginning of his proof.


Proof: Sufficient to show result for product of two integers. Let r = 4n+1 and
s =4m+1 for some integer m and n.Then......(I get the rest)


Thanks for the comments
Shadow89 is offline  
 
September 17th, 2017, 06:50 PM   #2
Senior Member
 
mrtwhs's Avatar
 
Joined: Feb 2010

Posts: 630
Thanks: 102

$\displaystyle a \cdot b \cdot c = (a \cdot b) \cdot c= d \cdot c$ where $\displaystyle d=a \cdot b$
Thanks from Shadow89
mrtwhs is offline  
September 17th, 2017, 07:13 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,572
Thanks: 379

You can get the case of n integers by induction. It's true for 2 integers. If you have n+1 integers $k_1 k_2 \dots k_{n+1}$ you can use the associative law to write it as $(k_1 k_2 \dots k_n)k_{n+1}$. By the induction hypothesis the part in parens is of the form 4n+1. We can now apply the 2-integer version to get the general result.

Last edited by Maschke; September 17th, 2017 at 07:17 PM.
Maschke is offline  
September 17th, 2017, 07:21 PM   #4
Senior Member
 
Joined: May 2016
From: USA

Posts: 803
Thanks: 319

Quote:
Originally Posted by Shadow89 View Post
In class the professor proved that the product of 2 or more integers of the form 4n + 1, is of the same form.

I understand most of the proof, but in class he said it was sufficient to prove the statement with only two integers, but I do not understand why you only need two integers to prove it. I'll give the beginning of his proof.


Proof: Sufficient to show result for product of two integers. Let r = 4n+1 and
s =4m+1 for some integer m and n.Then......(I get the rest)


Thanks for the comments
Suppose you have n factors, each of the form 4n + 1, where n > 2..

$x = \displaystyle \prod_{j=1}^nf_j \text {, where } f_j = 4i_j + 1 \text { with } i_j \in \mathbb Z.$

But you have a theorem that says

$u,\ v \in \mathbb Z \implies (4u + 1)(4v + 1) \in \mathbb Z \text { and } \exists \ w \in \mathbb Z \text { such that } 4w + 1 = (4u + 1)(4v + 1).$

$\displaystyle \therefore x = f_1 * f_2 * \prod_{j=3}^nf_j = s_1 * \prod_{j=3}^nf_j.$

And s_1 is in the proper form by the theorem. So

$\displaystyle n = 3 \implies x = s_1 * f_3 = s_2.$ And s_2 is in the proper form.

$\displaystyle n > 3 \implies x = s_1 * \prod_{j=3}^nf_j = s_1 * f_3 * \prod_{j=4}^nf_j = s_2 * \prod_{j=4}^nf_j.$

And s_2 is in the proper form.

You can keep doing that until you run out of factors.

Last edited by JeffM1; September 17th, 2017 at 07:23 PM.
JeffM1 is offline  
September 17th, 2017, 07:23 PM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,973
Thanks: 2295

Math Focus: Mainly analysis and algebra
Nothing new to add, but maybe stated a bit more clearly:

If $ab$ is of the form $4m + 1$ (by the proof for two numbers), then $(ab)c$ is also of the form $4n + 1$ by the same proof. Thus $abc$ is of the form $4n+1$.

The same idea (via Maschke's comment about induction gets you to the same result for as many numbers as you wish.
v8archie is offline  
September 17th, 2017, 07:23 PM   #6
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,973
Thanks: 2295

Math Focus: Mainly analysis and algebra
Nothing new to add, but maybe stated a bit more clearly:

If $ab$ is of the form $4m + 1$ (by the proof for two numbers), then $(ab)c$ is also of the form $4n + 1$ by the same proof. Thus $abc$ is of the form $4n+1$.

The same idea (via Maschke's comment about induction gets you to the same result for as many numbers as you wish.
v8archie is offline  
September 23rd, 2017, 01:35 PM   #7
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,731
Thanks: 707

Of course (just to stick my oar in) (4n+ 1)(4m+ 1)= 4mn+ 4n+ 4m+ 1= 4(mn+ n+ m)+ 1 so is of the form "4n+ 1" where the integer "n" is now mn+ n+ m.
Country Boy is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
sufficient



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
p.d.f of sufficient statistic calypso Advanced Statistics 0 December 27th, 2015 12:46 AM
Necessary vs Sufficient condition matisolla Algebra 1 May 26th, 2015 03:38 AM
necessary & sufficient condition of utility maximization helloprajna Economics 4 August 30th, 2013 03:46 AM
Sufficient Sample Size for Binomial Distribution Code2004 Probability and Statistics 1 August 6th, 2013 12:55 PM
Minimal sufficient statistic & MLE wawataiji Advanced Statistics 0 December 10th, 2012 03:41 AM





Copyright © 2017 My Math Forum. All rights reserved.