Finding Integer Solutions to Diophantine Equations

[bomba923]

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\<br /> \exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \left\{ {0,1, \ldots ,p - 1} \right\} \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

 

[matt grime]

As stated that looks trivially false. I am assuming that your bracket is the legndre/jacobi symbol, and if so it is plus or minus 1 (or zero), the a_i are a *subset* (sets cannot have repeated elements) of {0,..p-1}, and as such just picking r large will do. The largest that sum could possibly be is 1+2+..+p-1 = (p-1)(p-2)/2

 

[MathematicalPhysicist]

i think it's true because it's limited to the existential quantifier, and thus we can find at least one sequence of a's which are subset to p-1's.

for example, p=2 q=1 n=2 r=a0+a1*2+a2*4, and thus r is natural, and you can find a combination where {a0,a1,a2} are subset of {0,1} like a0=a1=0 a2=1, etc.

 

[matt grime]

That is assuming that that symbol means the fraction p/q. As this was a number theory thread I assumed differently.

In anycase, it is still false as stated, and you cannot have the set {a0,a1,a1} as a subset of {0,1} the former has 3 elements the latter has two elements. Sets cannot have repeated elements. {0,0,1} is not a set. But almost certainly that is being too picky.

Replace it with

$$a_i \in \{0,..,p-1\}$$

perhaps.

 

[MathematicalPhysicist]

isn't the set {0,0,1} equivalent to {0,1}?

p.s
i know that repetition doesn't affect the set itself, but i didn't know it wasn't allowed.

 

[matt grime]

To be honest I forget these days, or rather I would avoid using such ambiguous notation as to avoid having to figure out what was meant. You could well be right.

 

[Zurtex]

The question doesn't make too much sense, it confuses sequences and sets, repetition of elements and the cardinality is somewhat ambiguous. But however you meant it I think this will apply:Pretty trivial proof that it is true for r > 2, let p = q

$$r = \sum_{k=0}^n a_k$$

In other words, given an element of the natrual numbers can it be represented by a sum of smaller numbers, e.g 1 + 2 = 3, 1 + 3 = 4. All you have to do is prove that inductively, which is pretty trivial.

 

[daveb]

As Matt Grime pointed out, the way it's written, it isn't true (even if it is fractions). Let p=2, q=1, r=100. Then the coefficients a(i) are either 0, 1 or 2, and 100 = a(0) + a(1)*3/2 + a(2)*9/4 cannot be satisfied. It's written as for every p, q, and r.

 

[bomba923]

Pretty trivial proof that it is true for r > 2, let p = q

$$r = \sum_{k=0}^n a_k$$

!Zurtex, in the original post, it clearly states "p > q > 0"

You CANNOT have p=q
----------------------------------

As stated that looks trivially false. I am assuming that your bracket is the legndre/jacobi symbol

No!--it's just the fraction...p/q !

As Matt Grime pointed out, the way it's written, it isn't true (even if it is fractions). Let p=2, q=1, r=100. Then the coefficients a(i) are either 0, 1 or 2, and 100 = a(0) + a(1)*3/2 + a(2)*9/4 cannot be satisfied. It's written as for every p, q, and r.

WHere did you get the 3/2 & 9/4 ?? If p=2 and q=1, you will have a₀*(2/1) + a₁*(4/1) + ... etc!

*Daveb, if p=2 and q=1, then p/q = 2
And in that case, any a_i is either 0 or 1.

But...let's take your example, where p=2, q=1, and r=100.
The sequence {a₀,a₁,...,a_n} = {0,0,1,0,0,1,1}
as
0(1) + 0(2) + 1(4) + 0(8) + 0(16) + 1(32) + 1(64) = 100Or, take the example where p=3, q=2, and r=100, in which case any a_i is indeed 0,1, or 2. The sequence {a₀,a₁,...,a_n} = {1,0,2,1,0,0,2,1,2}
as
1(1) + 0 + 2(3/2)² + 1(3/2)³ + 0 + 0 + 2(3/2)⁶ + 1(3/2)⁷ + 2(3/2)⁸ = 100*Just one more example: let p=7, q=4, and r=23.
The sequence {a₀,a₁,...,a_n} = {2,5,4}
as
$$2 + 5\left( {\frac{7}{4}} \right) + 4\left( {\frac{7}{4}} \right)^2 = 23$$

Btw, q=1 and r ≤ p are just the trivially true cases.

To be honest I forget these days, or rather I would avoid using such ambiguous notation as to avoid having to figure out what was meant. You could well be right.

No problem! I'll rewrite this less ambiguously:

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\<br /> \exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}\;{\text{where }}\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

Now, true or false?

 

[matt grime]

Why do you insist on writing the a_i as a set?

$$\exists a_i, 0\leq i \leq n, a_i \in \{0,\ldots,p-1\}$$

 

[bomba923]

Why do you insist on writing the a_i as a set?

$$\exists a_i, 0\leq i \leq n, a_i \in \{0,\ldots,p-1\}$$

I don't. I intend to write it as a finite sequence of integers, each of which is between 0 (zero) and p-1 inclusively. Doesn't {a₀,a₁,...,a_n} denote a finite sequence?

*If not, how would you denote a finite sequence?

 

[Muzza]

*If not, how would you denote a finite sequence?

See the second line of his post?

 

[matt grime]

$$(a_i)_{i=0}^{i=n}$$

is how you more formally write sequences: round brackets with the limits marked top and bottom, though it is not usually necessary.

 

[MathematicalPhysicist]

shouldn't they be curled brackets {}?

 

[matt grime]

I wouldn't have thought so. Curly braces are reserved for sets, and sets are neither ordered, nor allow repetition, unlike sequences.

 

[shmoe]

$$\{a_i \}_{i=0}^{n}$$ is sometimes used to denote an ordered sequence, though not always. Sometimes <> are used. Sometimes () are used. There's no universal notation here.

 

[Zurtex]

!Zurtex, in the original post, it clearly states "p > q > 0"

You CANNOT have p=q

Sorry, I mis-read that as p > 0 and q > 0.

Trivial Proof 2

n = 0
p > q > r > 0
a₀=r

Think you can complete the rest.

 

[daveb]

WHere did you get the 3/2 & 9/4 ??...Or, take the example where p=3, q=2, and r=100

That's what I meant to write...oops. As Matt pointed out, {...} is generally for sets, especially since you initially wrote it as one being a subset (rather than a sequnce) of the other. The way you rewrote it now makes more sense.

 

[bomba923]

Sorry, I mis-read that as p > 0 and q > 0.

Trivial Proof 2

n = 0
p > q > r > 0
a₀=r

Think you can complete the rest.

Zurtex,
I never said r MUST be less than p!
Again, q=1 and r<p are just the trivially true cases!

What about q > 1 and r > p ?

shouldn't they be curled brackets{}?

Apparently not, but that's what I thought! :shy:

$$(a_i)_{i=0}^{i=n}$$
is how you more formally write sequences: round brackets with the limits marked top and bottom, though it is not usually necessary.

Alright, I'll rewrite the statement again (hopefully for the last time! unless other problems with semantics occur):

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\,{\text{ where }} \, p > q > 0, \hfill \\<br /> \exists \left( {a_k } \right)_{k = 0}^n \,{\text{ where }}\,\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

~Now, true or false?

 

[Zurtex]

Alright, I'll rewrite the statement again (hopefully for the last time! unless other problems with semantics occur):

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\,{\text{ where }} \, p > q > 0, \hfill \\<br /> \exists \left( {a_k } \right)_{k = 0}^n \,{\text{ where }}\,\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

~Now, true or false?

The question is still a little ill-posed, I'm not exactly sure what you want. Is the question:

Can you generate any natural number r for every pair (p,q)?Edit: made a mistake, deleted itYour question seemed to me to be, can you generate a pair (p,q) to satisfy any given natural number r. Which I can prove in several trivial cases, and I 've shown the other question to be false with a trivial counter example, so what do you want?!?

Zurtex,
I never said r MUST be less than p!
Again, q=1 and r<p are just the trivially true cases!

What about q > 1 and r > p ?

I never said you said that, however it is also trivially true in the case of:

q = anything
and
p > r

With a little more work that can be broadened a little to an easy proof (almost trivial) for:

q= anything
and
p > r or p = r

Hmm, I think I may of misunderstood you though, when you say: "q=1 and r<p" are you referring to 2 different cases? It really doesn't look like it, but it is also trivially true of the case of:

q = 1

 

[daveb]

Zurtex, it still works trivially if r < p since you can dictate that a(0) = r and then take all other a(k) = 0.

 

[shmoe]

This can be handled using the Euclidean algorithm, similar to integer base expansions.

Define $$r_1,a_0$$ by $$r=pr_{1}+a_0$$, where $$0\leq a_0 \leq p-1$$ and $$r_{1}\geq 0$$ (the Euclidean algorithm). Note $$r_1 < r$$

In general define $$r_{k+1},a_{k}$$ by $$qr_{k}=pr_{k+1}+a_{k}$$, where $$0\leq a_k \leq p-1$$ and $$r_{k+1}\geq 0$$. Note again that $$r_{k+1}<r_{k}$$ as q<p and $$a_{k}\geq 0$$.

Therefore this algorithm terminates eventually with $$qr_{n}=p0+a_{n}$$, say.

Work backwards,

$$r_{n}=a_{n}\frac{1}{q}$$
$$r_{n-1}=a_{n}\frac{p}{q^2}+a_{n-1}\frac{1}{q}$$
...
$$r_{1}=a_{n}\frac{p^{n-1}}{q^n}+\ldots+a_{1}\frac{1}{q}$$
$$r=a_{n}}\frac{p^{n}}{q^n}+\ldots+a_{1}\frac{p}{q}+a_{0}$$

the a's are the coefficients you wanted to prove existed.

 

[Zurtex]

Zurtex, it still works trivially if r < p since you can dictate that a(0) = r and then take all other a(k) = 0.

I know, I stated that.
o.k, I think I can gather from the responces give, it's a bit difficult to guess what the person is actually asking!.

So, let's examine:

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\,{\text{ where }} \, p > q > 0, \hfill \\<br /> \exists \left( {a_k } \right)_{k = 0}^n \,{\text{ where }}\,\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

~Now, true or false?

Lets try the question in words to make more sense:For all p,q and r in the natrual numbers where p > q
(The author doesn't seem to realize that all natrual numbers are greater than 0)
Does there exist a sequence of length n + 1, such that all elements of the sequence are less than p and the sequence can be used as co-efficents of the sum from 0 to n of powers of p/q and that is equal to r.Read over that a couple of times and get it clear in your head, you'll see the question can be written more clearly and mathematically like so:$$\text{Given }p, q, r \in \mathbb{N} \, \text{and} \, p > q$$

$$\text{Does there exist a sequence of integers} \, \left(a_i \right)_{i=0}^{n} \, \text{such that} \, 0 \leq a_i < p$$

$$\text{and} \, r = \sum_{i=0}^n a_i \left( \frac{p}{q} \right)^i \, \text{?}$$Which if you think about is proven to be true by shmoe, it's really a sum of powers of rational numbers, just like out decimal system, because they don't need to approach any irrational number then they can do it in a finite sum.

I would have guessed something like (p,q,r)=(4,3,10) might of needed an infinite sum, but seemingly not, learn something new every day.

 

[bomba923]

The question is still a little ill-posed, I'm not exactly sure what you want.

I'll write it out simply:

For any natural numbers p,q,r where p>q>0,

there exists a sequence {a₀, a₁,...,a_n} whose terms (i.e., ALL a_i) are all integers between zero(0) and p-1

such that
$$r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k }$$
------------------------------

Can you generate any natural number r for every pair (p,q)?

In which case, no, take the pair (p,q) = (4,1) and take the r = 3. There exists no way you can generate 3 from that pair and it's easy to show.

And here is why this assertion is incorrect:

Let p = 4 and q = 1. You have the pair (4,1). The sequence corresponding to r=3 is simply {3}

Because:

1) All elements sequence are integers between zero and p-1 inclusively.

2) '3' is an integer inclusively between zero(0) and p-1. In other words,
$$3 \in \left[ {0,p - 1} \right] \cap \mathbb{Z} \Rightarrow 3 \in \left[ {0,3} \right] \cap \mathbb{Z}$$

3) The sequence a₀=3 (a sequence with one term) satisfies
$$r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k }$$
when p=4, q=1, and r=3. Why? Because:
$$\sum\limits_{k = 0}^0 {a_k \left( {\frac{p}{q}} \right)^k } = a_0 \left( {\frac{4}{1}} \right)^0 = 3\left( 1 \right) = 3$$

I never said you said that, however it is also trivially true in the case of:

q = anything
and
p > r

With a little more work that can be broadened a little to an easy proof (almost trivial) for:

q= anything
and
p > r or p = r

Hmm, I think I may of misunderstood you though, when you say: "q=1 and r<p" are you referring to 2 different cases? It really doesn't look like it, but it is also trivially true of the case of:

q = 1

Zurtex, the statement is trivially true when r <= p or q=1.

But, have you considered when BOTH r > p and q > 1 ?
Or to put it briefly, when r > p > q > 1 ?
-----------------------------------------------
Here are some examples where r > p > q > 1:

1) p=7, q=4, r=39. Thus, the sequence is {4,6,1,4}, as
$$4 + 6\left( {\frac{7}{4}} \right) + 1\left( {\frac{7}{4}} \right)^2 + 4\left( {\frac{7}{4}} \right)^3 = 39$$

2) p=13, q=10, r=29. Thus, the sequence is {3,7,10}, as
$$3 + 7\left( {\frac{{13}}{{10}}} \right) + 10\left( {\frac{{13}}<br /> {{10}}} \right)^2 = 29$$

3) p=17, q=11, r=94. Thus, the sequence is {12,4,16,11}, as
$$9 + 4\left( {\frac{{17}}{{11}}} \right) + 16\left( {\frac{{17}}{{11}}} \right)^2 + 11\left( {\frac{{17}}{{11}}} \right)^3 = 94$$

...it still works trivially if r < p since you can dictate that a(0) = r and then take all other a(k) = 0.

It seems as though people here are still preoccupied with the trivially true cases

So, I'll rewrite this statement to remove ALL trivially true cases :

$$\begin{gathered}<br /> \forall p,q,r \in \mathbb{N}\;{\text{where }}r > p > q > 1, \hfill \\<br /> \exists \left( {a_k } \right)_{k = 0}^n \;{\text{where }}\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\<br /> {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}<br /> {q}} \right)^k } \hfill \\ <br /> \end{gathered}$$

~Now, true or false?

 

[bomba923]

Zurtex---I see you've edited your post!

 

[Zurtex]

I've tried to clear a bit in my above post, but because you can't preview LaTeX it didn't come out right, refresh the page and it should be fine now.

Also I made a mistake in an above post that I removed at the same time someone else was quoting, which is where the inconsistency comes from.

Well, all done now, question answered, that was a headache. Well done shmoe

 

[bomba923]

I would have guessed something like (p,q,r)=(4,3,10) might of needed an infinite sum, but seemingly not, learn something new every day.

Just a sum of three terms:
$$2 + 2\left( {\frac{4}{3}} \right) + 3\left( {\frac{4}{3}} \right)^2 = 10$$

-----------------------------------
*A final question:

Now that we know the statement is true,
is there a non-brute force method (formula or algorithm)
of finding the sequence, given (p,q,r) ?[/size]

In particular, I'm trying to find the (21,20,200) sequence

 

[shmoe]

Now that we know the statement is true,
is there a non-brute force method (formula or algorithm)
of finding the sequence, given (p,q,r) ?[/size]

Yes, see post 22. If that counts as brute force to you, you're going to have to explain what you mean by "brute force".