interesting math problem

[Fly]

The prime decompositions of different integers m and n involve the same primes. The integers m+1 and n+1 also have this property. Is the number of such pairs (m,n) finite or infinite?

[CowsFTW]

Yes, the number of such pairs is finite or infinite...
but that's probably not what you meant [img]/images/graemlins/smile.gif[/img]

[Drag]

Infinite.

If k is a positive integer, then pairs:
[m,n] -> [ (2k)^2-1 , (2k+2)^2-1]
[m+1, n+1] -> [(2k)^2 , (2k+2)^2]

will have that required property of decomposition.

[bigpooch]

This is not correct. For example, with k=5, you have m=99
and n=143 but 13 divides 143 but not 99.

[Drag]

[ QUOTE ]
This is not correct. For example, with k=5, you have m=99
and n=143 but 13 divides 143 but not 99.

[/ QUOTE ]

They are both divided by 11.

Just decompose it as a difference of squraes: a^2-b^2=(a-b)(a+b)

[tshort]

[ QUOTE ]
[ QUOTE ]
This is not correct. For example, with k=5, you have m=99
and n=143 but 13 divides 143 but not 99.

[/ QUOTE ]

They are both divided by 11.

Just decompose it as a difference of squraes: a^2-b^2=(a-b)(a+b)

[/ QUOTE ]

99 = 3 x 3 x 11
143 = 11 x 13

3 doesn't divide 143 and 13 doesn't divide 99

[bigpooch]

Very likely infinite. If you believe the Lenstra-Pomerance-
Wagstaff conjecture about the number of Marsenne primes
less than 2^x-1 being asymptotic to (e^gamma)(log_base2(x)),
not only are there an infinity of Marsenne primes, but a
function that describes asymptotically how many:

http://en.wikipedia.org/wiki/Lenstra...aff_conjecture


Now, suppose q is a Marsenne prime, i.e., q+1 = 2^p for
some prime p>=2 and q is also a prime (an odd prime).

With m=q-1, m+1=q, n+1=q^2, n=q^2-1=(q+1)(q-1)=(2^p)m.

Then, m is even and clearly m and n have the same prime
factors. Also, trivially, n+1 and m+1 have the same prime
factors (namely, q).

[KipBond]

[ QUOTE ]
[ QUOTE ]
This is not correct. For example, with k=5, you have m=99
and n=143 but 13 divides 143 but not 99.

[/ QUOTE ]

They are both divided by 11.

Just decompose it as a difference of squraes: a^2-b^2=(a-b)(a+b)

[/ QUOTE ]

OP:

[ QUOTE ]
The prime decompositions of different integers m and n involve the same primes. The integers m+1 and n+1 also have this property. Is the number of such pairs (m,n) finite or infinite?

[/ QUOTE ]

Not just "one of the same prime", but (all of) the same primes. For example:

m = 2, n = 8

m = 2^1
n = 2^3
---> both share the same primes

m+1 = 3, n+1 = 9

m+1 = 3^1
n+1 = 3^2
---> both share the same primes

[Fly]

bigpooch,

I am looking for a solution using only high school math.

[thylacine]

[ QUOTE ]
The prime decompositions of different integers m and n involve the same primes. The integers m+1 and n+1 also have this property. Is the number of such pairs (m,n) finite or infinite?

[/ QUOTE ]

Here's a related question. What are all the pairs of numbers (k,k+1) such that one is a power of 2 and the other is a power of 3.

Examples are (1,2), (2,3), (3,4), (8,9). Are there any others. Anyone know? Does anyone know of techniques to answer questions like this? Is it some standard number theory, or is it really difficult?