×

# 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
3 years, 7 months ago

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 · 3 years, 7 months 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. · 3 years, 7 months ago

psi(2011)=2010=2*1005. Maybe you can use this. · 3 years, 7 months ago

$$2011 \mid 3^{1005} + 1$$ or $$2011 \mid 3^{1005} - 1$$ · 3 years, 7 months ago

@Anh Huy N. Do you want to prove the latter or the former? Your title contradicts what you said. · 3 years, 7 months ago

By Wolfram Alpha, you want to prove the former. :) · 3 years, 7 months ago

@ann huy N.,can u explain me your approach to the problem? · 3 years, 7 months 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$$ ) · 3 years, 7 months 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 · 3 years, 7 months ago