September 17th, 2017, 07:42 PM  #1 
Newbie Joined: Sep 2017 From: San Diego Posts: 8 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 
September 17th, 2017, 07:50 PM  #2 
Senior Member Joined: Feb 2010 Posts: 633 Thanks: 104 
$\displaystyle a \cdot b \cdot c = (a \cdot b) \cdot c= d \cdot c$ where $\displaystyle d=a \cdot b$

September 17th, 2017, 08:13 PM  #3 
Senior Member Joined: Aug 2012 Posts: 1,661 Thanks: 427 
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 2integer version to get the general result.
Last edited by Maschke; September 17th, 2017 at 08:17 PM. 
September 17th, 2017, 08:21 PM  #4  
Senior Member Joined: May 2016 From: USA Posts: 857 Thanks: 348  Quote:
$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 08:23 PM.  
September 17th, 2017, 08:23 PM  #5 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,091 Thanks: 2360 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. 
September 17th, 2017, 08:23 PM  #6 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,091 Thanks: 2360 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. 
September 23rd, 2017, 02:35 PM  #7 
Math Team Joined: Jan 2015 From: Alabama Posts: 2,875 Thanks: 766 
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.


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 01:46 AM 
Necessary vs Sufficient condition  matisolla  Algebra  1  May 26th, 2015 04:38 AM 
necessary & sufficient condition of utility maximization  helloprajna  Economics  4  August 30th, 2013 04:46 AM 
Sufficient Sample Size for Binomial Distribution  Code2004  Probability and Statistics  1  August 6th, 2013 01:55 PM 
Minimal sufficient statistic & MLE  wawataiji  Advanced Statistics  0  December 10th, 2012 04:41 AM 