Help, please... what are the factors of p^4+1 ?
Joaquim Nogueira
I did a search by computer (I did not go very far, due to lack of programming skills) and this conjecture seems to work. But a proof seems to be out of reach. My former supervisor had also problems with this question...
This could help to generalize a result in a paper in which we are working.
Is this really a difficult question or are we simply not smart enough???
Please help!
Joaquim Nogueira
Gottfried Helms
Hmm, I did no analysis for your problem; but
concerning your programming skills - you may consider
simply to download Pari/Gp and let it do the hard
work for you.
Example:
forprime(p=2,59, \
p4=p^4+1;fp=factor(p4); \
print(p," ",p4," ",fp[,1]," ",fp[,1] % p) \
)
gives this list (though not tabularized):
p p^4+1 factors of p^4+1 moduli factors (mod p)
--------------------------------------------------------
3 82 [2, 41]~ [2, 2]~
5 626 [2, 313]~ [2, 3]~
7 2402 [2, 1201]~ [2, 4]~
11 14642 [2, 7321]~ [2, 6]~
13 28562 [2, 14281]~ [2, 7]~
17 83522 [2, 41761]~ [2, 9]~
19 130322 [2, 17, 3833]~ [2, 17, 14]~
23 279842 [2, 139921]~ [2, 12]~
29 707282 [2, 353641]~ [2, 15]~
31 923522 [2, 409, 1129]~ [2, 6, 13]~
37 1874162 [2, 89, 10529]~ [2, 15, 21]~
41 2825762 [2, 137, 10313]~ [2, 14, 22]~
43 3418802 [2, 17, 193, 521]~ [2, 17, 21, 5]~
47 4879682 [2, 97, 25153]~ [2, 3, 8]~
53 7890482 [2, 17, 232073]~ [2, 17, 39]~
59 12117362 [2, 17, 593, 601]~ [2, 17, 3, 11]~
--
---
Gottfried Helms, Kassel
Pubkeybreaker
It is clearly true for p = 3 mod 4. (factors of p^4 + 1 are 1 mod 4
by Euler/Lagrange)
For p =1 mod 4, I would start by factoring p^4 + 1 over Q( (-1)^1/4)
and looking at norms.
I am not sure if this will lead to your result.
hagman
> On Dec 6, 7:05 am, Joaquim Nogueira <j...@fct.unl.pt> wrote:
>
> > I am searching a way to show that the only factors of p^4+1 (when p is an odd prime) that are congruent to 1 (mod p) is the number itself and... 1.
> > I did a search by computer (I did not go very far, due to lack of programming skills) and this conjecture seems to work. But a proof seems to be out of reach. My former supervisor had also problems with this question...
>
> > This could help to generalize a result in a paper in which we are working.
>
> > Is this really a difficult question or are we simply not smart enough???
>
> It is clearly true for p = 3 mod 4. (factors of p^4 + 1 are 1 mod 4
> by Euler/Lagrange)
Too fast for me, how does d = 1 mod 4 exclude that d = 1 mod p ?
Jeremy Boden
Or...
Does it help to know that p^4 + 4 = (p^2 + 2p + 2)(p^2 - 2p + 2)?
This is true for all p >= 1 (p not necessarily prime).
(Factorize P^4 + 4 in C and simplify).
--
Jeremy Boden
"64 bits good, 32 bits bad"
Red
p^4+1 =(kp+1)(ap^3+bp^2+cp+d)
and then tried to show that k=1 or k=p^3 ?.
A lot of things drop out nicely, when you
set the term-to-term equality above.
quasi
wrote:
Yes to both (in my opinion).
Yes -- it's probably a really difficult question.
Yes -- we're probably not smart enough (where "we" means the human
race). At least not at present.
It's not even clear to me that the conjecture is true.
However, if it is true, then assuming certain regularities, one may be
able to argue heuristically that the probability of a counterexample
is zero.
quasi
quasi
I suspect the polynomial p^4 +1 could be replaced by any irreducible
integer polynomial in the variable p, of degree at least 3, and the
problem would still be too hard.
In fact, I'll make two counter-conjectures ...
Conjecture (1):
If f is an irreducible, univariate, integer polynomial of degree at
least 3, then there are infinitely many positive integers n such that
f(n) has a positive integer factor d = 1 (mod n), and where 1 < d <
f(n).
Conjecture (2):
Conjecture (1) remains true if we require n to be prime.
quasi
quasi
Correction: and where 1 < d < abs(f(n)).
Phil Carmody
If p^4+1 has a proper factor == 1 (mod p), then it must have
a factor of the form (a*p+1) with 0<a<p. (if a>=p, then look
at its cofactor.)
(a*p+1)'s cofactor can be expressed as (b*p^2+c*p+1) with b,c<p
(a*p+1)*(b*p^2+c*p+1) = b*a*p^3 + (c*a + b)*p^2 + (a + c)*p + 1
That must be == 1 (mod p^2), so c=p-a
(a*p+1)*(b*p^2+(p-a)*p+1) = (b+1)*a*p^3 + (b+1-a^2)*p^2 + 1
That must be == 1 (mod p^3), so b=a^2-1
(a*p+1)*((a^2-1)*p^2+(p-a)*p+1) = a^3*p^3 + 1 = p^4+1
So a^3 = p, which contradicts p's primeness.
[]
OK, it's 6am, and I can't sleep, so the above might be complete
bollocks, but to me it made sense at the time.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
quasi
<thefatphi...@yahoo.co.uk> wrote:
>Pubkeybreaker <pubkey...@aol.com> writes:
>> On Dec 6, 7:05 am, Joaquim Nogueira <j...@fct.unl.pt> wrote:
>> > I am searching a way to show that the only factors of p^4+1 (when p is an odd prime) that are congruent to 1 (mod p) is the number itself and... 1.
>> > I did a search by computer (I did not go very far, due to lack of programming skills) and this conjecture seems to work. But a proof seems to be out of reach. My former supervisor had also problems with this question...
>> >
>> > This could help to generalize a result in a paper in which we are working.
>> >
>> > Is this really a difficult question or are we simply not smart enough???
>>
>>
>> It is clearly true for p = 3 mod 4. (factors of p^4 + 1 are 1 mod 4
>> by Euler/Lagrange)
>>
>> For p =1 mod 4, I would start by factoring p^4 + 1 over Q( (-1)^1/4)
>> and looking at norms.
>> I am not sure if this will lead to your result.
>
>
>If p^4+1 has a proper factor == 1 (mod p), then it must have
>a factor of the form (a*p+1) with 0<a<p. (if a>=p, then look
>at its cofactor.)
>
>(a*p+1)'s cofactor can be expressed as (b*p^2+c*p+1) with b,c<p
>
>(a*p+1)*(b*p^2+c*p+1) = b*a*p^3 + (c*a + b)*p^2 + (a + c)*p + 1
>
>That must be == 1 (mod p^2), so c=p-a
>
>(a*p+1)*(b*p^2+(p-a)*p+1) = (b+1)*a*p^3 + (b+1-a^2)*p^2 + 1
>
>That must be == 1 (mod p^3),
>
>so b=a^2-1
No, a^2 - 1 need not be less than p.
All you can say is b = a^2 - 1 (mod p)
>(a*p+1)*((a^2-1)*p^2+(p-a)*p+1) = a^3*p^3 + 1 = p^4+1
>
>So a^3 = p, which contradicts p's primeness.
>
>OK, it's 6am, and I can't sleep, so the above might be complete
>bollocks, but to me it made sense at the time.
Actually, I had already tried along the exact same lines.
In my opinion, it's not elementary.
In fact, in my opinion, it's not even true (but proving will also not
be elementary).
quasi
Phil Carmody
Good catch, quasi.
> >(a*p+1)*((a^2-1)*p^2+(p-a)*p+1) = a^3*p^3 + 1 = p^4+1
> >
> >So a^3 = p, which contradicts p's primeness.
> >
> >OK, it's 6am, and I can't sleep, so the above might be complete
> >bollocks, but to me it made sense at the time.
>
> Actually, I had already tried along the exact same lines.
>
> In my opinion, it's not elementary.
>
> In fact, in my opinion, it's not even true (but proving will also not
> be elementary).
It's a fascinating little teaser. I may throw it at a few
mathematically oriented friends...
quasi
Well, of course, if it's not true, then proving that it's not true
wold only require one counterexample, and if such a counterexample
could be found, the "proof" that the OP's claim is false would be
trivial.
What I meant was, as indicated in my conjecture (2), that I actually
believe that there are infinitely many counterexamples, however
proving _that_ claim, if it's true, is probably not elementary.
quasi
hagman
Assume p prime, 0<a<p, 0<b<p, 0<c<p and
(ap+1)(bp^2 + cp +1) = p^4 +1
Then
ab p^3 + (b+ac) p^2 + (a+c) p + 1 = p^4 +1
implies c=p-a.
Thus we have
(ap+1)((b+1)p^2 - ap +1) = p^4 +1
or
a(b+1) p + (b+1-a^2) = p^2
p^2 + a^2 = (b+1)(ap+1)
Since the left side is not divisible by p, we conclude that
b+1 is not p, hence 1<d<p with d:=b+1 and
p^2 + a^2 = d(ap+1)
Note that d is simply the remainder of a^2 mod p.
If a^2 < p this means d = a^2 and
p^2 + a^2 = a^3 p + a^2
a^3 = p -- contradiction.
Hence a^2 > p.
If d=e^2 is a perfect square, 0<e, this excludes a=e and thus
implies a = p-e, hence
p^2 + (p-e)^2 = e^2 ((p-e)p+1)
which leads to e^2 = 2 -- contradiction.
If a < p/d, we have a^2 = d(ap+1)-p^2 < d -- contradiction.
Hence r = ad-p is a positive integer.
Then
p^2 + a^2 = d(ap+1)
p^2 + (r+p)^2/d^2 = p(r+p) + d
(r+p)^2 = (rp+d)d^2
(r-p)^2 = d^3 + rp*(d^2-4)
If d=2, this implies (r-p)^2 = 8 -- contradiction.
Otherwise, it implies that d^3 (and hence d) is a square mod d^2-4.
d^2-4 is a multiple of 5 if d=2 mod 5 or d=3 mod 5, but 2,3 are not
squares mod 5, hence d=2 mod5, d=3 mod 5 can be excluded.
More generally, if q is a prime divisor of either d-2 or d+2,
then d must be a square mod q.
Hence all prime divisors of d-2 must be +-1 mod 8 (i.e. 7, 17,
23, ...)
and all prime divisors of d+2 must be +-3 mod 8 (i.e. 3, 5, 11,
13 ...).
Especially d itself is either 1 mod 8 or 3 mod 8.
This leaves only comparatively few candidates for d, especially
all small ones are ruled out:
9 -- is a square
11 -- 3|d-2
17 -- 3|d-2
19 -- 7|d+2
25 -- is a square
27 -- 5|d-2
33 -- 7|d+2
35 -- 3|d-2
41 -- 3|d-2
Possible d values are 43, 51, 73, 99, 105, 115, 129, ...
Of course this immediately excludes all primes p<=43.
Since 43 is not a square mod 47, we even conclude p>=53.
Someone will probably volunteer to write a program that
walks through all primes p in sequence, checks per quadratic
reciprocity if a candidate d<p is a square mod p, and then
whether the corresponding square roots mod p produce a solution
to the original problem.
While pen and paper were enough to exclude a substantial
nunmber of primes, it is quite possible that larger primes
can produce a solution.
My findings should simplify such a search for a counterexample,
but it is of course also possible that none exists :)
hagman
quasi
After a little thought, I no longer believe either of my above
conjectures. In fact, I think the following reversal makes more sense,
giving some hope for the OP's claim.
Here is a revised conjecture ...
If f is a nonzero univariate integer polynomial, there are at most
finitely many positive integers n such that f(n) has a positive
integer factor d = 1 (mod n), and where 1 < d < abs(f(n)).
quasi
quasi
Whoops, I need more restrictions ...
This should work:
If f is an irreducible univariate integer polynomial, there are at
quasi
wrote:
I now think there's a decent chance that the OP's claim is actually
true.
I checked all primes p < 300,000.
No counterexample so far.
quasi
quasi
Conjecture:
If f is an irreducible univariate integer polynomial, there are at
most finitely many integers n such that f(n) has an integer factor d,
where 1 < abs(d) < abs(f(n)), and d = 1 (mod n).
Question:
Does there exist an irreducible univariate integer polynomial f, of
degree at least 3, such that, for all integers n, if d is an integer
factor of f(n), with 1 < abs(d) < abs(f(n)), then d is not congruent
to 1 (mod n)?
quasi
Gerry
> On Fri, 7 Dec 2007 06:27:42 -0800 (PST), hagman <goo...@von-eitzen.de>
> wrote:
>
>
>
>
>
> >On 6 Dez., 13:05, Joaquim Nogueira <j...@fct.unl.pt> wrote:
> >> I did a search by computer (I did not go very far, due to lack of programming skills) and this conjecture seems to work. But a proof seems to be out of reach. My former supervisor had also problems with this question...
>
> >> This could help to generalize a result in a paper in which we are working.
>
> >> Is this really a difficult question or are we simply not smart enough???
>
> >> Please help!
>
> >> Joaquim Nogueira
>
> > (ap+1)(bp^2 + cp +1) =p^4+1
> >Then
> > abp^3 + (b+ac)p^2 + (a+c)p+1=p^4+1
> >implies c=p-a.
> >Thus we have
> > (ap+1)((b+1)p^2 - ap +1) =p^4+1
> >or
> > a(b+1)p+ (b+1-a^2) =p^2
> > p^2 + a^2 = (b+1)(ap+1)
> >Since the left side is not divisible byp, we conclude that
> >b+1is notp, hence1<d<pwith d:=b+1and
> > p^2 + a^2 = d(ap+1)
> >Note that d is simply the remainder of a^2 modp.
>
> > p^2 + a^2 = a^3p+ a^2
> >Hence a^2 >p.
>
> >If d=e^2 is a perfect square, 0<e, this excludes a=e and thus
> >implies a = p-e, hence
> > p^2 + (p-e)^2 = e^2 ((p-e)p+1)
> >which leads to e^2 = 2 -- contradiction.
>
> >If a <p/d, we have a^2 = d(ap+1)-p^2 < d -- contradiction.
>
> >Hence r = ad-p is a positive integer.
> >Then
> > p^2 + a^2 = d(ap+1)
> > (r+p)^2 = (rp+d)d^2
> > (r-p)^2 = d^3 + rp*(d^2-4)
> >If d=2, this implies (r-p)^2 = 8 -- contradiction.
> >Otherwise, it implies that d^3 (and hence d) is a square mod d^2-4.
> >squares mod 5, hence d=2 mod5, d=3 mod 5 can be excluded.
> >More generally, if q is a prime divisor of either d-2 or d+2,
> >then d must be a square mod q.
> >23, ...)
> >and all prime divisors of d+2 must be +-3 mod 8 (i.e. 3, 5, 11,
> >13 ...).
>
> >This leaves only comparatively few candidates for d, especially
> >all small ones are ruled out:
> >9 -- is a square
> >11 -- 3|d-2
> >17 -- 3|d-2
> >19 -- 7|d+2
> >25 -- is a square
> >27 -- 5|d-2
> >33 -- 7|d+2
> >35 -- 3|d-2
> >41 -- 3|d-2
> >Possible d values are 43, 51, 73, 99, 105, 115, 129, ...
>
> >Since 43 is not a square mod 47, we even concludep>=53.
>
> >Someone will probably volunteer to write a program that
> >reciprocity if a candidate d<pis a square modp, and then
> >whether the corresponding square roots modpproduce a solution
> >to the original problem.
>
> >While pen and paper were enough to exclude a substantial
> >nunmber of primes, it is quite possible that larger primes
> >can produce a solution.
> >My findings should simplify such a search for a counterexample,
> >but it is of course also possible that none exists :)
>
> I now think there's a decent chance that the OP's claim is actually
> true.
>
>
> No counterexample so far.
>
> quasi- Hide quoted text -
>
> - Show quoted text -
Hi
in case you are still looking check out :
Binomial Number a^n+b^n from Wolfram Mathworld
and the integer sequence A001227:
"Number of factors in the factorization of the polynomial x^n+1 over
the integers."
Regards
Gerry
Joaquim Nogueira
I am writing just to thank you all for your answers. It seems that my question was not easy...
Just some extra notes: the related question about the powers p^3+1 (p odd prime) is the following: all its factors congruent to 1 (mod p) must have the form p+1 or p^2-p+1 ? The answer is "yes": there is a proof. About the powers p^5+1 the question: all its factors congruent to 1 (mod p) must have the form p+1 or p^4-p^3+p^2-p+1 has answer "no".
When p=7 the factors 22 and 764 of 7^5+1 = 16808 are not of this form; when p=17 the factors 426 and 3333 of 17^5+1 = 1419858 are not of this form.
Is there any formula that shows when do these exceptions arise? I haven't thought about it.
Joaquim Nogueira
quasi
wrote:
>Hi,
Let me try to give a precise statement of the problem:
Find all positive integers k such that, for all odd primes p, the only
positive integer factors of p^k + 1 which are congruent to 1 mod p are
those that are equal to g(p), where g(x) is a monic integer polynomial
factor of x^k + 1.
For k <= 100, the only values of k which satisfy the above conditions
are k = 1, 2, 3 and possibly 4, 6, 64, 94.
Since we don't even have a proof that k = 4 satisfies the above
conditions, it's not very likely that we can provably determine the
complete set of such values of k.
quasi
Don Coppersmith
A descent argument seems to work.
Define
x = p,
x^4+1 = (x*w+1)*(x*y+1),
satisfying the inequalities
1 < w < x < y.
We will develop a smaller instance.
Since (x*w+1) divides (x^4+1) and (x^4*w^4-1),
we know (x*w+1) divides their sum, x^4*(w^4+1).
Since GCD(x*w+1,x^4)=1, we know
(x*w+1) divides w^4+1.
The quotient q=(w^4+1)/(x*w+1) is an integer.
We can compute the quotient mod w, since
GCD(w,x*w+1)=1, and we find q=1 mod w.
Thus q=1+w*v.
Check that x>w implies w>v. We now have
w^4+1 = (w*v+1)*(w*x+1),
satisfying the inequalities
v < w < x.
We can continue this descent as long as v>1.
v is nonnegative.
So we stop when v=1 or 0.
If we reach v=1, then since GCD(w^4+1,w*1+1) is 1 or 2,
we know w=0 or 1, so we should have stopped earlier.
If instead we reach v=0, then x=w^3.
Let b=w. Both x and w are multiples of b.
We can check that y is also a multiple of b,
and if we climb back up the chain all the x values
are multiples of b. In particular p is divisible by b.
But p is prime.
Don Coppersmith
quasi
wrote:
Ingenious and skillful.
Very nice.
quasi