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.

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

[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?

Calvin Lin Staff - 8 years, 2 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.

Anh Huy Nguyen - 8 years, 2 months ago

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

Bhargav Das - 8 years, 2 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$ )

Anh Huy Nguyen - 8 years, 2 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}$

Calvin Lin Staff - 8 years, 2 months ago

thanks.

Bhargav Das - 8 years, 2 months ago

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

Sambit Senapati - 8 years, 2 months ago

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

Zi Song Yeoh - 8 years, 2 months ago

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

Zi Song Yeoh - 8 years, 2 months ago

@Zi Song Yeoh – By Wolfram Alpha, you want to prove the former. :)

Zi Song Yeoh - 8 years, 2 months ago

Math	Appears 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}$

Problem: Prove that 31005≡=−1(mod 2011) 3^{1005} \equiv =-1 (\mod 2011) 31005≡=−1(mod2011)

Comments

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