Number theory problems, help please

I'm having problems with the following questions, and some hints on what to do would be greatly appreciated :biggrin:

Find integers

x,y

such that

95x + 432y = 1

I am pretty sure that I need to reverse the Euclidean algorithm to find values for x and y. I carried out the algorithm in the normal manner and found that

gcd(95,432) = 1

. I tried to reverse the algorithm by re-arranging each equation of the algorithm from the form

r_{n-2} = r_{n-1}q_n + r_n

to

r_{n} = r_{n-2} - r_{n-1}q_n

and substituting

r_{n-1}

into each equation until I got one in terms of a and b (where a and b are 432 and 95 respectively), but my answer was clearly wrong. Does anyone know what I'm doing wrong?
Also, is there an easy was to extend this to three integers?

Prove that if

g_{1}, g_{2}, ...

are integers >1 then every natural number can be expressed uniquely in the form

a_{0} + a_{1}g_{1} + a_{2}g_{1}g_{2} + ... + a_{k}g_{1}g_{2}...g_{k}

where the

a_j

are integers satisfying

0\le a_j < g_{j+1}

I have though about this one for a bit and I don't know how to go about approaching it at all. Any hints would be great :biggrin:

I have some more but I'm going to think about them a bit more. I'll post them in here when I inevitably get nowhere :p:

Reply 1

KAISER_MOLE

7

This is good for your first question

For your second question, every number up to g(1) can just be expressed as a(0) , what about every number up to g(2)? tis like a number base system I guess

Reply 2

ad absurdum

OP

2

Thank you for your help :smile:

I've got the first one okay now, I think I was just making mistakes when I was trying to do it with algebra. Whatever I was doing wrong, it worked when I done it with the actual numbers :smile:

Unforunately I'm still not getting this second one :frown:

Reply 3

KAISER_MOLE

7

Generally-

a(0) + a(1)g(1) + a(2)g(1)g(2) + a(3)g(1)g(2)g(3) +......+a(m)g(1)...g(m) = Z/g(1)g(2)...g(m)g(m+1)Z (It's residue class)

Check this by maximising your a's to their full extent, you should get the supremum of the residue class you are looking for (this is due to the way in which the a's are bounded).

If we start from the beginning, a(0) goes up to g(1)-1 . If a(1) was unbounded, you could express every natural number just using the first two terms. As it is, the sum of the first two terms are bounded above by g(1)g(2), but you can hit g(1)g(2) whole residue class up to that point. So this argument keeps going and going until we get some unbounded a(m) ( a(k) for example :p:

)

Reply 4

Popcorn

KAISER_MOLE

Generally-

a(0) + a(1)g(1) + a(2)g(1)g(2) + a(3)g(1)g(2)g(3) +......+a(m)g(1)...g(m) = Z/g(1)g(2)...g(m)g(m+1)Z (It's residue class)

Check this by maximising your a's to their full extent, you should get the supremum of the residue class you are looking for (this is due to the way in which the a's are bounded).

If we start from the beginning, a(0) goes up to g(1)-1 . If a(1) was unbounded, you could express every natural number just using the first two terms. As it is, the sum of the first two terms are bounded above by g(1)g(2), but you can hit g(1)g(2) whole residue class up to that point. So this argument keeps going and going until we get some unbounded a(m) ( a(k) for example :p:

)

I have absolutely no idea what you're on about. Sounds interesting though. :smile:

Reply 5

ad absurdum

OP

2

KAISER_MOLE

Generally-

a(0) + a(1)g(1) + a(2)g(1)g(2) + a(3)g(1)g(2)g(3) +......+a(m)g(1)...g(m) = Z/g(1)g(2)...g(m)g(m+1)Z (It's residue class)

Check this by maximising your a's to their full extent, you should get the supremum of the residue class you are looking for (this is due to the way in which the a's are bounded).

If we start from the beginning, a(0) goes up to g(1)-1 . If a(1) was unbounded, you could express every natural number just using the first two terms. As it is, the sum of the first two terms are bounded above by g(1)g(2), but you can hit g(1)g(2) whole residue class up to that point. So this argument keeps going and going until we get some unbounded a(m) ( a(k) for example :p:

)

Thank you

I've not got the solution yet but I understand better now, hopefully I'll get it when I try tomorrow (too tired now).

I also got the one three integers that I was stuck with, if anyone wants to try the problem it is:
Find integers x, y, z such that

35x + 55y + 77z = 1

Number theory problems, help please

Related discussions

Articles for you