# Problem: Prove that $$3^{1005} \equiv =-1 (\mod 2011)$$

Hello everybody, I'm having difficulty proving 3^1005 +1 is divisible by 2011, which is one step to solve this problem:

Prove that there exists x,y in {1,2,...,1005} such that x^2+3y^2-3 is divisible by 2011.

Thanks a lot.

Note by Anh Huy Nguyen
6 years ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

[As Zi Song pointed out, your discussion should say that $$3^{1005}+1$$ is divisible by 2011. Please update that.]

I'm assuming that you are familiar with concepts like Euler's Theorem and (Gauss Law of) Quadratic Reciprocity. You should be able to fill in the details. This approach is pretty standard.

[As Sambit suggested] Since 2011 is prime, we have $$\phi (2011) = 2010$$. By Euler's theorem, we know that $$3^{2010} \equiv 1 \pmod{2011}$$. Let $$3^{1005} = x$$, then $$0 \equiv x^2 - 1 \equiv (x-1)(x+1) \pmod{2011}$$, so $$x \equiv \pm 1 \pmod{2011}$$ (since 2011 is prime).

If $$x \equiv 1 \pmod{2011}$$, then $$[ 3^{503} ] ^2 \equiv 3^{1006} \equiv 3 \pmod{ 2011}$$, so 3 is a quadratic residue. However, since $$2011 \equiv 7 \pmod{12}$$, this contradicts the fact that the Legendre symbol $$\left( \frac {3}{2011} \right) = -1$$.

Pop quiz: Does this show that 3 is a primitive root modulo 2011? Why, or why not?

Staff - 6 years ago

You have my gratitude, Calvin. Legendre is the least thing I think of, but I guess it's inevitable in some cases. A good lesson for me.

- 6 years ago

@ann huy N.,can u explain me your approach to the problem?

- 6 years ago

My deepest apology, the title is what I want to prove. Many thanks to Zi Song Y.

@Bhargav D: This is my approach to the original problem. Let $$A=\{1,2,...,1005\}$$.

Consider two sets $$B=\{ x^2 - 3 | x \in A\} ; C=\{ -3y^2 | y \in A\}$$.

It's easy to see that:

• No two elements of B are $$\equiv (\mod 2011)$$. The same for C.

• No element of C is divisible by 2011. The same for B (1).

(1) is not obvious and needs to be proven. Still the only way I can think of is, assume there is a number x in A satisfying $$x^2 - 3 \vdots 2011 \Rightarrow x^2 \equiv 3 \Rightarrow x^{2010} \equiv 3^{1005} \equiv -1$$, which contradicts Fermat's theory $$x^{2010} \equiv 1 (\mod 2011)$$.

So to prove (1) we need to prove $$3^{1005} \equiv -1$$, which is true but ....

Continuing with the original problem. We consider 2 cases:

Case 1: There are two numbers $$a \in B, b \in C$$ satisfying $$a \equiv b \Rightarrow x^3 - 3 \equiv -3y^2$$ (QED).

Case 2: For all $$a \in B, b \in C$$, a and b are not $$\equiv (\mod 2011)$$:

Since $$|B|=|C|=1005 \Rightarrow B \cup C$$ is a set of 2010 elements, and can be expressed as $$T=\{a_1,a_2,...,a_{2010} \}$$ where $$a_i \equiv i (\mod 2011)$$.

Therefore $\sum_{x \in T} x \equiv \sum_{i=1}^{2010}i \equiv 0 ( \mod 2011)$ However, by calculation, $$\sum_{x \in T} x$$ is not divisible by 2011.

(Its exact result is $$-3015 - 2\sum_{i=1}^{1005} i^2$$ )

- 6 years ago

This problem depends on how you think about it, and what you know.

For example, I simply set $$x =2, y\equiv \pm 3^{502} \pmod{2011}$$ (where I use $$\pm$$ to ensure that it lies in the domain). This gives

$x^2 + 3y^2 - 3 \equiv 4 + 3 \times 3^{1004} - 3 \equiv 3^{1005} + 1\equiv 0 \pmod{2011}$

Staff - 6 years ago

thanks.

- 6 years ago

psi(2011)=2010=2*1005. Maybe you can use this.

- 6 years ago

$$2011 \mid 3^{1005} + 1$$ or $$2011 \mid 3^{1005} - 1$$

- 6 years ago

@Anh Huy N. Do you want to prove the latter or the former? Your title contradicts what you said.

- 6 years ago

By Wolfram Alpha, you want to prove the former. :)

- 6 years ago

×