343 as a linear combination of 1729 and 4096?

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 2792 Views - Last Post: 07 October 2013 - 07:37 AM

#1 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 10:10 AM

First I couldnt figure out what exactly the question asked. Then I realized, it wants me to find a and b such that
343 = 1729*a + 4096*b. A little more thinking, told me that 343 has to be a gcd of two numbers. I may be wrong. I used Euclidean Algorithm to find the gcd of 1729 and 4096 to see if there is any connection with 343. they are relatively prime, meaning GCD of them is 1. "a" and "b" are integers.

Can someone give me an example on how to do such a problem?

This post has been edited by deprosun: 06 October 2013 - 01:09 PM


Is This A Good Question/Topic? 0
  • +

Replies To: 343 as a linear combination of 1729 and 4096?

#2 Dormilich  Icon User is offline

  • 痛覚残留
  • member icon

Reputation: 3393
  • View blog
  • Posts: 9,591
  • Joined: 08-June 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 12:04 PM

without any further constraints, there is no single answer to this problem. simple Algebra would give you a function b = f(a), for which each pair {a,b} solves the equation.
Was This Post Helpful? 1
  • +
  • -

#3 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 12:48 PM

Can we use chinese remainder theorem?
Was This Post Helpful? 0
  • +
  • -

#4 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 01:08 PM

Forgot to mention that a and b are integers.

This post has been edited by deprosun: 06 October 2013 - 01:08 PM

Was This Post Helpful? 0
  • +
  • -

#5 Dormilich  Icon User is offline

  • 痛覚残留
  • member icon

Reputation: 3393
  • View blog
  • Posts: 9,591
  • Joined: 08-June 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 01:18 PM

that’s one important point!
Was This Post Helpful? 2
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 01:42 PM

So gcd(1729, 4096) = 1, which implies that there exist constants a, b in Integers such that 1729a + 4096b = 1. What would happen if you multiplied both sides by 343?
Was This Post Helpful? 1
  • +
  • -

#7 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 01:58 PM

One of them is a negative number
Was This Post Helpful? 1
  • +
  • -

#8 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 02:25 PM

View Postmacosxnerd101, on 06 October 2013 - 03:42 PM, said:

So gcd(1729, 4096) = 1, which implies that there exist constants a, b in Integers such that 1729a + 4096b = 1. What would happen if you multiplied both sides by 343?


If I multiply both sides by 343, it will be: (1729 * 343)a + (4096 * 343)b = 343. I still don't see it :/
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 02:26 PM

Rearrange the parentheses. Think about the associative property here. Then do a substitution.
Was This Post Helpful? 1
  • +
  • -

#10 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 02:45 PM

I think I found it. I found the linear combination of the gcd=1. Which was 1 = 4096*729 - 1729*1727.

Using your equation, I multiplied both sides with 343, and turns out, it fits. So my a and b would be 729 and -1727 respectively.
Is this correct?

This post has been edited by deprosun: 06 October 2013 - 03:16 PM

Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 04:23 PM

You think it be pretty easy to test by simply plugging those values in the equation and seeing if it matches the expected answer. Apparently not.
Was This Post Helpful? 3
  • +
  • -

#12 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 04:34 PM

Nope. Not correct. Those a and b values are for finding ax + by = gcd(x, y). You didn't apply my suggestions appropriately. It's pretty simple algebra. You want to maintain x and y. How would you modify a and b in the equation 1729a + 4096b = 1 (ie., gcd(a, b )), to get 1729(ka) + 4096(kb ) = 343?
Was This Post Helpful? 1
  • +
  • -

#13 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 05:49 PM

I completely failed at explain what I wanted to explain. I apologize, here is what I did:
Once I found this:
1 = 4096*729 - 1729*1727

I multiplied both sides by 343,
343 = 4096*729*343 - 1729*1727*343

Then concluded that my a and b are 729*343 and 1727*343 respectively.
Does this look correct?

View PostAdamSpeight2008, on 06 October 2013 - 06:23 PM, said:

You think it be pretty easy to test by simply plugging those values in the equation and seeing if it matches the expected answer. Apparently not.


That would be painful, just used Euclidean Algorithm.
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 06:20 PM

Quote

That would be painful, just used Euclidean Algorithm.

He doesn't mean attack the problem using brute force and ignorance. He means take the equation and evaluate the numbers. Do you get the expected result? Adam is telling you to check your own work.
Was This Post Helpful? 2
  • +
  • -

#15 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7293
  • View blog
  • Posts: 12,125
  • Joined: 19-March 11

Re: 343 as a linear combination of 1729 and 4096?

Posted 06 October 2013 - 09:15 PM

Second the check your own work. If you're not sure that your test is correct, ask about the test, but at least make an effort.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2