I restate my challenge.

kind regards
JB

Using Fermat's little theorem
x^n - x = 0 if n is prime and also
y^n - y = 0 if n is prime

mod(x^n, n) = mod(x, n)
mod(x^n plus y^n, n) = mod(x plus y, n)

If A = mod(x plus y, n) and A does not = 0 then
A / A = 1

Its not so easy to prove that all the prime factors are also 1 mod n

kind regards
JB

Using Fermat's little theorem
x^n - x = 0 mod(n) if n is prime and also
y^n - y = 0 mod(n) if n is prime

kind regards
JB

x=5, y=9, n=11
x^n plus y^n = 31,429,887,734 which divided by 14 (x plus y)
gives 2,244,991,981 which is 1 mod(11) and has prime factors
p1=23, p2=67, p3=89 and p4=16,369 and all are 1 mod(11)

I haven't found a counter example yet, alas nor a proof

kind regards
JB
kind regards
JB

Likewise. I ran experiments with Java - none produced a counter example.

Take a look at

https://groups.yahoo.com/group/primenumbers/message/14223

and

https://groups.yahoo.com/group/primenumbers/message/14636

https://groups.yahoo.com/group/primenumbers/message/14637

private reply:

Yes.
If q divides a^(2p) - b^(2p) then it must divide (a^p-b^p) or (a^p+b^p); in either case, q = 2*k*p + 1, for some integer k > 0.

Odd case anyone?

I too had carried these out to huge numbers using Pari.

Have fun,

Cino

Let p|(a^n + b^n)/(a + b)

Claim 1: p != 2
Proof: a and b cannot both be even. So for a^n + b^n to be even they must both be odd. But then (a^n + b^n)/(a + b) = a^(n-1) + a^(n-2)*b + ... + b^(n-1), a sum of an odd number of odd terms, and hence an odd number.

Claim 2: (b, p) = 1.
Proof: If p | b then also p | a so that (a, b) != 1 contradiction.

Now let e be the greatest integer such that p^e | (a^n + b^n). In the following I shall work mod p^e. We have a^n + b^n ~ 0, so that (a/b)^n + 1 ~ 0 (this is allowed by claim 2). Rearranging gives ((a/b)^2)^n ~ 1. There are now 2 cases.

Case 1: (a/b)^2 ~ 1. Rearranging gives (a + b)(a - b) ~ 0, so there are 2 subcases:
Subcase 1: a + b ~ 0. Since p^e | a+b, p cannot divide (a^n + b^n) / (a + b), which is a contradiction.
Subcase 2: a - b ~ 0. Substituting gives 2b^n ~ 0, which is a contradiction by claims 1 and 2.

Case 2: Otherwise. By the Fermat-Euler theorem and the primality of n we now have n | (p-1) * p^(e-1). Since p != n (that would imply 0 ~ (x^n + y^n) ~ x + y mod n), n|(p-1). We therefore have the desired result: p ~ 1 mod n.

Thankyou

sfwc
<><

kind regards
JB

Thankyou

sfwc
<><

This is too brief for me to follow. How do you get to n ! (p-1) ?
By the Fermat-Euler theorem do you mean " x^n - x = k*n "? (where n is prime)

kind regards
JB

No. The Fermat-Euler theorem is a generalisation of the result you mention, also commonly known as Euler's theorem (but there are many other theorems which also go by the name of Euler's theorem). In the case in question, let k = phi(p^s) = (p-1) * p^(s-1). I shall continue to work modulo p^s. Let A = (a/b)^2

We have A^n ~ 1, and since A is coprime to p, we also have (directly by the Fermat-Euler theorem) that A^k ~ 1. So for any integers c and d we have A^(c*k + d*n) ~ 1. In particular, if e is the greatest common divisor of k and n, a pleasant theorem implies that A^e ~ 1. Now, e | n, and so since n is prime e = 1 or e = n. We have dealt with the possibility that A^1 ~ 1 in case 1, and so e = n. But also e|k and so finally n|k, which is the result you were asking about.

I hope that that helps.

Thankyou

sfwc
<><

Oh Well, back to the drawing board!

only one prime factor needs to be greater than x plus y to make
z^n which must be less than (x plus y)^n impossible

kind regards
JB

kind regards
JB

Enjoy

Thankyou

sfwc
<><

19 - 1 = 18 is a multiple of 3
kind regards
JB

x = 1
y = 2^4 * 7
y + x = 113
y - x = 3 * 37
n = 5

These numbers are pairwise coprime.

(x^5 + y^5)/(x + y) = 155959441 = 11^2 * 1288921

There are now no solutions with n = 3.

Thankyou

sfwc
<><

and x plus y cannot be a prime.

Lets go for both.

kind regards
JB

(x^n + y^n)/(x+y) = 4956281 = 11^2 * 40961

Thankyou

sfwc
<><

What conditions could be dropped if the function was restricted to primes to the n-1 th power?

kind regards
JB

>What conditions could be dropped if the function was
>restricted to primes to the n-1 th power?
I'm afraid I don't understand the question. What is the function to which you are referring?

Thankyou

sfwc
<><

Back in a month
take care

It is easy to prove that (x^n plus y^n)/(x plus y)
is of the form

A^2 - n * N * B^2 where A and B are mutually prime and N is squarefree i.e. prime factors of N are not repeated.

Is this enough to prove that the function A^2 - n * N * B^2
cannot be a square or any higher power i.e. ALL its prime factors are repeated the same number of times?

I don't think you will come up with an exception to this one.

take care

Thankyou

sfwc
<><

take care

Thankyou

sfwc
<><

y^(2*n)= 1 mod p

y^(p-1)= 1 mod p

2*n = p-1

p= 2*n plus 1

Even if the argument were valid, it does not answer my original criticism that it is not necessarily possible to multiply both sides by some power of x^n say x^(j*n) such that y^n * x^(j*n) = 1 mod p1. It would only cover a special case.

Thankyou

sfwc
<><

take care

As I understand it, you need them to eventually reach y^(-n) for your argument to work. Since, as you say, this isn't guaranteed, you need to refine your argument.

Sorry I took so long to reply; I've been on holiday.

Thankyou

sfwc
<><

now in mod p arithmetic, where p is a prime number, every integer (say x in this case) from 1 to p-1 has a recriprocal - meaning if x * b = 1 then b is the recriprocal of x.

Now (x^n plus y^n) = 0 mod p (as p is a factor)
Multiply both sides by b^n gives
(x*b)^n plus (y*b)^n = 0 mod p
as (x*b) = 1,
1 plus (y*b)^n = 0 mod p
Therefore (y*b)^n = (p-1) mod p
(y*b)^(2*n)= (p-1)^2 mod p
= p^2 -2*p plus 1 mod p
= 1 mod p
For some positive integer k
Thus(y*b)^(2*n*k) = 1 = (y*b)^(p-1) mod p
Thus (2*n*k) = (p-1) mod p
and p = 2*n*k plus 1 (mod p) which is the required result

Thanks to all who have helped!

>and p = 2*n*k plus 1 (mod p) which is the required result
This is not the required result; what is required is the much stronger statement p = 2*n*k + 1. For example, we have 7 = 2*5*2 + 1 (mod 7) but there is no integer k for which 7 = 2*5*k + 1.

Please note that (x^n + y^n) may have prime factors which are not of the form 2*n*k + 1, so any proof that (x^n + y^n)/(x+y) does not must take account of the denominator.

Thankyou

sfwc
<><

You are absolutely correct.

The interesting thing you point out actually makes the proof better.
If a^s = a^r (mod p)
where p is prime and a is not 0 or a multiple of p,
s = r (mod p-1) !!!
this is because a^(p-1) = 1 mod p

therefore if (b*y)^(2*n) = 1 = (b*y)^(p-1) in (mod p)

2*n = p-1 in mod (p-1) and 2*n*k = p-1 where k is a positive integer

then 2*n*k plus 1 = p

in your example 2^1 = 2^5 in mod 5
therefore 1 = 5 in mod 4 which it does!!!

take care and kind regards

The question was:

(a^n + b^n)/(a+b) = 1 (mod n)

Now Fermats little theorem says (n prime,gcd(a,n)=1,gcd(n,b)=1):
a^n-a = 0 (mod n)
b^n-b = 0 (mod n)

So :
(a^n-a) + (b^n-b) = 0 (mod n)

rearranging:
a^n + b^n = a+b (mod n)

If (a+b) =/= 0 (mod n) (as given in the question)
I can divide:

(a^n + b^n)/(a+b) = 1 (mod n)

to get the initial equation.

Anything wrong?

Gotti

Thankyou

sfwc
<><

> this is because a^(p-1) = 1 mod p
Sometimes we may have a^k = 1 mod p with 0 < k < p-1. For example, 2^3 = 1 mod 7 and 1^1 = 1 mod p for any p.

Another note: You have not used the fact that n is prime. But the theorem is false without this condition.

Thankyou

sfwc
<><

I don't suppose we can make anything of 2^5 = 2^2 mod 7
and 5 = 2 mod 3 ? ( 3 = (7-1)/2 )

We know that we can divide p-1 by d and we will get some quotient q and some remainder r satisfying p-1 = q*d + r, and with 0 <= r < q. But then we have by Fermat's Little Theorem that:
1 = a^(p-1) = (a^d)^q * a^r = a^r. Since q was the least positive integer with that property, we deduce that r isn't positive. That is, r = 0. So d really does divide p-1.

How does this help us? Well, the same argument shows that for any k with a^k = 1 mod p, d must divide k. Now we let a = x/y. You have shown already that (x/y)^2n = 1 mod p, so d divides 2n. Since n is prime, d must be either 1, 2, n or 2n. Now if d was n or 2n, we would be finished, since then we would know that n divided p-1 and we can prove separately that 2 also divides p-1.

What if d is 1 or 2? Well, in that case we know that (x/y)^2 = 1 mod p, so (x + y)(x - y) = x^2 - y^2 = 0 mod p, so either x + y is 0 mod p or x - y is 0 mod p. In the second case, x = y mod p, and so 0 = x^n + y^n = 2(x^n) mod p, which is impossible since 2x and p are coprime. But the first case is much more of a problem. It tells us that the denominator of (x^n + y^n)/(x+y) is also divisible by p, so that we can cancel a factor of p from the top and bottom. But then we don't know whether p divides the fraction (x^n + y^n)/(x + y) at all. And if it does, we learn nothing about p.

The way to get around this is to work modulo the highest power of p that occurs in the numerator. If x + y is 0 modulo that then we know for sure that p doesn't divide the fraction as a whole. The argument is quite similar, but instead of using Fermat's Little Theorem, you need Euler's generalisation which tells you that if a is coprime to p we have a^((p-1) * p^(k-1)) = 1 modulo p^k for any k >= 1. You should be able to put together a working argument based on that.

Thankyou

sfwc
<><

take care

If x plus y = 0 mod p then p divides x plus y.
It can be shown that x plus y and (x^n plus y^n)/(x plus y) have no common factors or are mutually prime. Therefore if p divides x plus y then it cannot divide (x^n plus y^n)/(x plus y).

If y - x = 0 mod p then x = y mod p and this is impossible.

Therefore d must divide n or 2n and d divides p-1
Finally if n divides p-1 and 2 divides p-1
Then 2*n*k = p-1 and
2*n*k plus 1 = p for some positive integer k

Thanks for that
take care

Thankyou for this neat simplification,

sfwc
<><

If x and y are relatively prime (have no common factors)
then x plus y will be relatively prime to both x and to y.
similarly y - x will be relatively prime to both x and to y.

Relatively prime relationships do not transfer.
If a is rp to b and b is rp to c
this does not imply a is rp to c.

If x, y and z are mutually prime this means that;
x is rp to y, x is rp to z, y is rp to z

If x is rp to y then x^n is rp to y^m where n and m are any positive integers (not 0)

NOW for x, y, (x plus y) and n being mutually prime and n also prime;

x^n plus y^n = (x plus y)* ...]]]

So what we have here is a recursive expression

where we can demonstrate that x and y and (x plus y) (also n for that matter) - are all mutually prime to each stage of the expression

So x plus y must be relatively prime to the term in the outside square brackets, what was required.
I hope this is satisfactory.

take care

x^n plus y^n = (x plus y)* ...]]]

So what we have here is a recursive expression

where we can demonstrate that x and y and (x plus y) (also n for that matter) - are all mutually prime to each stage of the expression

So x plus y must be relatively prime to the term in the outside square brackets, what was required.
I hope this is satisfactory.

take care

I am now convinced that all the prime factors of the expression are 1 (mod 2*n)
kind regards
JB

Is there a website reference that displays this Journal of TRIZ ?

As a matter of interest, why did you introduce the variable R in the first line of the proof yet never refer to it again?

take care