June 7th, 2017, 07:32 AM  #1 
Math Team 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 \ \ $ 
June 8th, 2017, 05:40 AM  #2 
Math Team 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 
June 8th, 2017, 06:52 AM  #3  
Senior Member Joined: Feb 2010 Posts: 637 Thanks: 106  Quote:
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.  
June 8th, 2017, 08:22 AM  #4 
Math Team 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. 
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:
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 nonresidue 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.  
June 10th, 2017, 05:03 AM  #6 
Math Team 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. 
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.

June 11th, 2017, 02:21 PM  #8 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 
The link does not work in my browser

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? 
June 12th, 2017, 07:55 AM  #10  
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233  Quote:
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  

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 