Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
3 votes

Comments

Sort by:

Top Newest

[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 - 4 years, 7 months ago

Log in to reply

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

Log in to reply

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

Sambit Senapati - 4 years, 7 months ago

Log in to reply

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

Zi Song Yeoh - 4 years, 7 months ago

Log in to reply

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

Zi Song Yeoh - 4 years, 7 months ago

Log in to reply

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

Zi Song Yeoh - 4 years, 7 months ago

Log in to reply

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

Bhargav Das - 4 years, 7 months ago

Log in to reply

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

Log in to reply

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

Log in to reply

thanks.

Bhargav Das - 4 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...