My Math Forum Why is it sufficient

 Number Theory Number Theory Math Forum

 September 17th, 2017, 06: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, 06:50 PM #2 Senior Member     Joined: Feb 2010 Posts: 643 Thanks: 110 $\displaystyle a \cdot b \cdot c = (a \cdot b) \cdot c= d \cdot c$ where $\displaystyle d=a \cdot b$ Thanks from Shadow89
 September 17th, 2017, 07:13 PM #3 Senior Member   Joined: Aug 2012 Posts: 1,772 Thanks: 481 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.
September 17th, 2017, 07:21 PM   #4
Senior Member

Joined: May 2016
From: USA

Posts: 919
Thanks: 368

Quote:
 Originally Posted by Shadow89 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.

 September 17th, 2017, 07:23 PM #5 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,228 Thanks: 2411 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, 07:23 PM #6 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,228 Thanks: 2411 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, 01:35 PM #7 Math Team   Joined: Jan 2015 From: Alabama Posts: 2,966 Thanks: 807 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post calypso Advanced Statistics 0 December 27th, 2015 12:46 AM matisolla Algebra 1 May 26th, 2015 03:38 AM helloprajna Economics 4 August 30th, 2013 03:46 AM Code2004 Probability and Statistics 1 August 6th, 2013 12:55 PM wawataiji Advanced Statistics 0 December 10th, 2012 03:41 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top