A number theory problem by Kushal Bose

Number Theory Level 4

Find the number of all positive integers $n \leq 2017$ such that

$\large 7 \mid n^2+n+1$

Note: Avoid the use of computer programming. Otherwise you will not get the fun.

The answer is 576.

2 solutions

Mark Hennings
Mar 17, 2017

Since $(n-1)(n^2+n+1) = n^3-1$ , we want to find integers $1 \le n \le 2017$ such that $n^3 \equiv 1 \pmod{7}$ but $n\not\equiv 1 \pmod{7}$ , namely numbers such that $n \equiv 2,4 \pmod{7}$ . Since $2017 = 7\times288+1$ , we deduce that there are $2\times288 = \boxed{576}$ such numbers.

I have a doubt

$n^3-1 \equiv 0 \pmod{7}$

If $n=8$ then $n^3-1$ is divisible by $7$ .But $n^2+n+1$ is not divisible by 7.

So, in your calculation there may be some solutions which are not allowable.

Kushal Bose - 4 years, 2 months ago

@Kushal Bose You are right but this answer escapes that as $n$ is not congruent to 1 modulo 7.

Dhruv Somani - 4 years, 2 months ago

Ohh Thanks.I missed out that

Kushal Bose - 4 years, 2 months ago

@Kushal Bose – There would be another $289$ integers $n$ between $1$ and $2017$ with $n \equiv 1 \pmod{7}$ , but $n^2 + n + 1 \equiv 3 \pmod{7}$ for each of those.

Mark Hennings - 4 years, 2 months ago

Why didn't you just verify directly that $n^2 + n = 1 \equiv 0 \pmod 7 \Leftrightarrow n \equiv 2, 4 \pmod{7}$ ?

What benefits do we get by looking at $n^3 - 1$ ?

Calvin Lin Staff - 4 years, 2 months ago

By looking at $n^3-1$ , we can think about cube roots of units modulo $7$ . We can then consider that the nonzero numbers in $\mathbb{Z}_7$ form a cyclic group of order $6$ , with generator $3$ , and hence the cube roots of unity (modulo $7$ ) are the even powers of $3$ , namely $1,2,4$ , so the roots we want are $2,4$ (modulo $7$ ).

If we just solve the congruence $n^2 + n + 1 \equiv 0 \pmod{7}$ by hand, we miss the chance to see how this problem could be extended, so that we can solve equations of the form $n^a + n^{a-1} + \cdots + n + 1 \equiv 0 \pmod{p}$ for positive integers $a$ and primes $p$ .

Mark Hennings - 4 years, 2 months ago

Barr Shiv
Nov 28, 2018

observe that only the numbers of the form 7x+2,7x+4 can be plugged in to n and divide by 7. from both we have 288 options therefore: 288×2=576

A number theory problem by Kushal Bose

The answer is 576.

2 solutions

0 pending reports