My Math Forum Elementary Number Theory question

 Number Theory Number Theory Math Forum

 June 7th, 2017, 06: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 \ \$ Thanks from greg1313
 June 8th, 2017, 04: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, 05:52 AM   #3
Senior Member

Joined: Feb 2010

Posts: 663
Thanks: 119

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

 June 8th, 2017, 07: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 01:31 AM.
June 9th, 2017, 01: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 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.

 June 10th, 2017, 04: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 04:18 AM.
 June 11th, 2017, 09: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, 01: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, 03: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, 06:55 AM   #10
Math Team

Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

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

 Tags elementary, number, question, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post greg1313 Math Books 15 April 29th, 2015 01:36 AM matqkks Number Theory 2 June 17th, 2013 10:40 AM earth Number Theory 5 October 9th, 2010 05:54 AM tinynerdi Number Theory 0 November 29th, 2009 10:01 PM tinynerdi Number Theory 0 November 29th, 2009 09:25 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top