Anyone really good at math/problem solving?

[thesurge]

Prove that there an infinite amount of positive integers (n), which are not divisible by any perfect square greater than 1, that divide 2005^n-1.

(sorry for poor phrasing)

I started a geometric sequence of all possible answers (theoretically).. but it didn't go anywhere...
wtf?

 

[her209]

Proof by contradiction is probably your best bet.

 

[chuckywang]

Working on the problem now....

 

[chuckywang]

I believe you can do it with a proof by induction, but I still need one minor detail to make my proof rigorous.

 

[thesurge]

err....

 

[DaveSimmons]

Are you sure you can afford to buy the proof from chuckywang? Since you aren't Diamond yet the fee is much higher.

 

[chuckywang]

Originally posted by: thesurge
err....

Want me to elaborate?

Obviously the numbers with this property must be in the form of p1*p2*p3*p4*...*p_k, where all the p_i's are prime and none of them equal to each other.

Base case: Obviously n=2 works.

Inductive step: Assume n=p1*p2*p3*p4*...*p_k has the desired property. Consider a prime factor of 2005^n-1 that is not any of the p_i's. Call this prime factor p_(k+1).

It is not hard to show that n*p_(k+1) also has the desired property with the application of Fermat's Little Theorem. However, the minor detail that is keeping this proof from being rigorous is the fact that we haven't shown that such a p_(k+1) actually exists. One would think it has to exist given the enormous magnitude of 2005^n-1, but I have yet to prove it.



Of course, this proof could be totally off base, and there is a much simpler proof.

 

[duragezic]

Yeah what class is this for? First looking at it I would think proof by induction, but depending what class it is and what you are learning ATM should give you a start. Most profs don't give you homework that has no relevance or is way beyond what you have learned. Besides I suck at induction. In my discrete class when it came to induction on tests, I just kinda BS'ed through to get partial credit and understood most everything else so I could afford to loose a few points.

 

[thesurge]

Its for a ~intermediate number theory class... I finally got it, so if anyone wants me to post the proof I can.