343 as a linear combination of 1729 and 4096?

• (2 Pages)
• 1
• 2

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

#1 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• 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

• 痛覚残留

Reputation: 4122
• Posts: 13,004
• 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.

#3 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• 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?

#4 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• 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

#5 Dormilich

• 痛覚残留

Reputation: 4122
• Posts: 13,004
• 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!

#6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12127
• Posts: 45,090
• 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?

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• 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

#8 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

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

Posted 06 October 2013 - 02:25 PM

macosxnerd101, 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

#9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12127
• Posts: 45,090
• 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.

#10 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• 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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• 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.

#12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12127
• Posts: 45,090
• 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?

#13 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• 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?

AdamSpeight2008, 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.

#14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12127
• Posts: 45,090
• 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.

#15 jon.kiparsky

• Screw Trump (before he screws you)

Reputation: 10599
• Posts: 18,097
• 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.

• (2 Pages)
• 1
• 2

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }