Re: a problem in elementary number theory

On 2007-10-31 07:02:01 -0400, "dmitry.sustretov@xxxxxxxxx" <dmitry.sustretov@xxxxxxxxx> said:

Thank you for reply.

Surely, this technique can be applied on the test. I wonder, if a
"real" solution can be obtained (suppose you did not have a list of
candidate numbers).

Well, this is how I would have done it without the list of candidate numbers, but you might still think it's cheating though.

I would try some examples first.

For p=7, we have
7^4-1 = (7^2+1)(7-1)(7+1) = 50 x 6 x 8 = 2^5 x 3 x 5^2.
So, I know the only primes I need to examines are 2, 3 and 5. It remains to find the highest power for each prime that will divide into p^4-1 for all p>5.

Arguing as in my other threads, Fermat's Little Theorem and an observation of the even factors conclude the answer must be divisible by 2^4 x 3 x 5. So, from the test case p=7, there is an extra factor of 2 and an extra factor of 5. But examining the right side of
p^4-1 = (p^2+1)(p-1)(p+1)
you can conclude that this extra factor of 2x5 must come from p^2+1 only. Reason: The factor of 5 cannot come from p-1 or p+1 since they are both even. The extra factor of 2 cannot come from p-1 or p+1 because exactly one of them is a multiple of 4.

Since p^2+1 always have a factor of 2, it remains to find a p such that p^2+1 cannot be divisible by 2^2 x 5. This is easy, pick the case for p=9. Then
9^2+1 = 82 = 2 x 41.
This concludes that the answer is 2^4 x 3 x 5 = 240.

There is probably some methods that does not need to exploit test cases. Looking forward to see how that is done.


On Oct 30, 10:39 pm, Kira Yamato <kira...@xxxxxxxxxxxxx> wrote:
On 2007-10-30 16:59:39 -0400, "dmitry.sustre...@xxxxxxxxx"
<dmitry.sustre...@xxxxxxxxx> said:

Hello,

I am stuck solving this problem from GRE Math training booklet:

Find the maximal integer x such that x divides p^4-1 for all prime
numbers p > 5.

[they actually have a list to choose from: 12, 30, 48, 120, 240]

Do you have any ideas?

--

-kira

.

Relevant Pages

  • Re: As the Crow flies.
    ... It means the product of the first, second and third primes. ... That is a feature of Legendre's technique. ... so, sieving is still a practical algorithm: it runs very fast, since it ... reasonable implementation of standard techniques. ...
    (talk.origins)
  • Re: As the Crow flies.
    ... Which is how many my algorithm took. ... be silly indeed to use Lehmer's algorithm to count primes up to 997. ... that's a meaningless endorsement of your technique. ...
    (talk.origins)
  • Re: Surrogate factoring explained
    ... Meaning, all but the largest are very small (say 12 digits at most), and the ... parameters I believe the work needed to factor a 512-bit RSA moduli by p-1 ... One could also consider primes such that p+1 is smooth, ...
    (sci.math)
  • Re: Surrogate factoring explained
    ... Meaning, all but the largest are very small (say 12 digits at most), and the ... parameters I believe the work needed to factor a 512-bit RSA moduli by p-1 ... One could also consider primes such that p+1 is smooth, ...
    (sci.crypt)
  • Re: Breaking RSA & Securing RSA
    ... "A Practical Analysis of the Elliptic Curve Factoring Algorithm". ... > two 512-bit primes, its fine to just pick random primes. ... > p-1 factorisation method be faster than quadratic sieve based methods ... In over 30 years of trials with P-1, ...
    (sci.crypt)