My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
Reply
 
LinkBack Thread Tools Display Modes
June 7th, 2017, 07:32 AM   #1
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Elementary Number Theory question

Show that $ \ \ 7 \ \ $ does not divide $ \ \ n^2 + 1 \ \ $ for any integer $ \ \ n \ \ $

Thanks from greg1313
agentredlum is offline  
 
June 8th, 2017, 05:40 AM   #2
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Hint: A possible approach is to use the theory of congruences

Of interest may be the following sequence in the Online Encyclopedia Of Integer Sequences

https://oeis.org/A192450

agentredlum is offline  
June 8th, 2017, 06:52 AM   #3
Senior Member
 
mrtwhs's Avatar
 
Joined: Feb 2010

Posts: 632
Thanks: 103

Quote:
Originally Posted by agentredlum View Post
Show that $ \ \ 7 \ \ $ does not divide $ \ \ n^2 + 1 \ \ $ for any integer $ \ \ n \ \ $

Maybe something like this.

In mod 7, $\displaystyle n$ must be in $\displaystyle \{0,1,2,3,4,5,6\}$

So $\displaystyle n^2$ must be in $\displaystyle \{0,1,2,4\}$

Thus, $\displaystyle n^2+1$ must be in $\displaystyle \{1,2,3,5\}$

Therefore, $\displaystyle n^2+1$ is never 0 mod 7.
Thanks from agentredlum
mrtwhs is offline  
June 8th, 2017, 08:22 AM   #4
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Yes, very good. A clear and precise explanation.

Did you look at the oeis link? It looks like 83 out of the first 108 natural numbers do not divide $ \ \ n^2 + 1 \ \ $ which is surprising to me. What are your thoughts about that?


Last edited by skipjack; June 9th, 2017 at 02:31 AM.
agentredlum is offline  
June 9th, 2017, 02:54 PM   #5
Senior Member
 
Joined: Nov 2010
From: Berkeley, CA

Posts: 174
Thanks: 35

Math Focus: Elementary Number Theory, Algebraic NT, Analytic NT
Quote:
Originally Posted by agentredlum View Post
Yes, very good. A clear and precise explanation.

Did you look at the oeis link? It looks like 83 out of the first 108 natural numbers do not divide $ \ \ n^2 + 1 \ \ $ which is surprising to me. What are your thoughts about that?

I think you're wondering why there are so many numbers n such that -1 is not a square mod n (as opposed to the number of n such that -1 is a square mod n). Here's a sketch of an explanation. Please post again if you'd like to see more details.

The condition on n is equivalent to the congruence

$x^2 \equiv -1 \pmod{n}$

not having a solution for $x$ (We also say that -1 is a quadratic non-residue mod n.). Write n in its canonical prime decomposition:

$n=2^{a_1}3^{a_2} \cdots p_k^{a_k}$

For the purpose of this explanation, disregard 2 if it divides n. As is often the case, 2 has to be handled separately. Then it's known that the preceding congruence has a solution if and only if each of the congruences

$x^2 \equiv -1 \pmod{p_i}$

has a solution. It's known that

$x^2 \equiv -1 \pmod{p}$

(where p is an odd prime) has a solution if $p \equiv 1 \pmod{4}$ and does not have a solution if $p \equiv 3 \pmod{4}$.

We conclude that the original congruence does not have a solution if just one of the ${p_i}\equiv 3 \pmod{4}$. Conversely, the original congruence has a solution only if all the ${p_i} \equiv 1 \pmod{4}$. Evidently, there are more of the former than the latter.
Thanks from agentredlum
Petek is offline  
June 10th, 2017, 05:03 AM   #6
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Thank you for your nice reply. I did not know that there must be a solution for all $ \ \ p_i \ \ $ of the prime factorization of the divisor.

Very interesting ... so if the divisor contains at least one prime of the form $ \ \ 4r + 3 \ \ $ then it will not divide $ \ \ n^2 + 1 \ \ $

On the flipside ... a natural number like $ \ \ 2 \times 5 \times 13 = 130 \ \ $ is sure to divide $ \ \ n^2 + 1 \ \ $ because all the prime factors of $ 130 \ \ $ divide $ \ \ n^2 + 1 \ \ $

Is that right? Please feel free to post any other details you see fit.


Last edited by agentredlum; June 10th, 2017 at 05:18 AM.
agentredlum is offline  
June 11th, 2017, 10:49 AM   #7
Senior Member
 
Joined: Nov 2010
From: Berkeley, CA

Posts: 174
Thanks: 35

Math Focus: Elementary Number Theory, Algebraic NT, Analytic NT
Yes, your statements are correct. For more details on moving back and forth between congruences whose moduli are a single prime, to moduli that are multiple powers of a prime and to the general case, see this link.
Petek is offline  
June 11th, 2017, 02:21 PM   #8
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

The link does not work in my browser
agentredlum is offline  
June 11th, 2017, 04:17 PM   #9
Senior Member
 
Joined: Nov 2010
From: Berkeley, CA

Posts: 174
Thanks: 35

Math Focus: Elementary Number Theory, Algebraic NT, Analytic NT
Does this link work?

https://www.johndcook.com/blog/quadratic_congruences/

If not, what error message, if any, do you get?
Petek is offline  
June 12th, 2017, 07:55 AM   #10
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
Originally Posted by Petek View Post
Does this link work?

https://www.johndcook.com/blog/quadratic_congruences/

If not, what error message, if any, do you get?
This link is also non functional in my browser.

I do not own a working computer, using a PS3. The error is probably resulting from the PS3 browser's inability to decode Adobe but this is speculation on my part. This has been going on for many years , 10 years at least and I'm not the only one with this problem.

The error is ...

The page cannot be displayed. (80710a06)

ty for your concern in this matter
agentredlum is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
elementary, number, question, theory



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Book on elementary number theory greg1313 Math Books 15 April 29th, 2015 02:36 AM
What to include on a first elementary number theory course? matqkks Number Theory 2 June 17th, 2013 11:40 AM
2 elementary number theory problems.... earth Number Theory 5 October 9th, 2010 06:54 AM
elementary number theory without zero or negative numbers 2 tinynerdi Number Theory 0 November 29th, 2009 11:01 PM
elementary number theory without zero or negative numbers tinynerdi Number Theory 0 November 29th, 2009 10:25 PM





Copyright © 2017 My Math Forum. All rights reserved.