| |
 |
|
|
Science Forum Index » Mathematics Forum » Proofs Questions...
Page 1 of 1
|
| Author |
Message |
| Gerard Matthew |
 Posted: Thu May 01, 2008 3:30 pm |
|
|
|
Guest
|
Good Day,
I'm trying to get a heads up on how I should tackle a particular
proof.
Prove an integer n > 1 has the properties that n|(35m + 26) and n|(7m
+ 3) for some integer m. What is n?
I'm trying to go down the route of using the Euclidean Algorithm to
solve this problem; however, I am getting stuck. I substituted K for
7m + 3 and said that
n| 5K + 11 and n|K
then i tried
gcd(K, 5K+11)....but I'm stuck here.
Could someone direct me to the right path.
- Gerard. |
|
|
| Back to top |
|
| Gerard Matthew |
| Posted: Thu May 01, 2008 4:56 pm |
|
|
|
Guest
|
On May 1, 9:41 pm, William Hale <h...@tulane.edu> wrote:
Quote: In article
d38853d2-d3c7-465e-a2f3-f6a8da53d...@m36g2000hse.googlegroups.com>,
Gerard Matthew <calibis...@gmail.com> wrote:
Good Day,
I'm trying to get a heads up on how I should tackle a particular
proof.
Prove an integer n > 1 has the properties that n|(35m + 26) and n|(7m
+ 3) for some integer m. What is n?
I'm trying to go down the route of using the Euclidean Algorithm to
solve this problem;
I think congruence approach would be easier:
35m + 26 = 0 (mod n)
7m + 3 = 0 (mod n)
etc.
however, I am getting stuck. I substituted K for
7m + 3 and said that
n| 5K + 11 and n|K
From n|K, conclude 5*n | 5 * K. Use that fact now with n | 5K + 11.
then i tried
gcd(K, 5K+11)....but I'm stuck here.
Should I assume basedon the gcd(A,B) = gcd(A, B-A) that it would boil
down to the gcd(K,11) and since the prove states for n> 1 that the
only option for the gcd of K and 11 is 1....?
Quote: I think you mean you have:
n divides gcd(K, 5K+11).
But, gcd(K, 5K+11) = gcd(K, 5K - K +11) = gcd(K, 4K+11) = etc
by using the fact that gcd(A, B) = gcd(A, B - A).
Could someone direct me to the right path.
- Gerard.
|
|
|
| Back to top |
|
| Harun Al-Rashid |
| Posted: Thu May 01, 2008 5:08 pm |
|
|
|
Guest
|
Quote: Good Day,
I'm trying to get a heads up on how I should tackle a
particular
proof.
Prove an integer n > 1 has the properties that n|(35m
+ 26) and n|(7m
+ 3) for some integer m. What is n?
I'm trying to go down the route of using the
Euclidean Algorithm to
solve this problem; however, I am getting stuck. I
substituted K for
7m + 3 and said that
n| 5K + 11 and n|K
And so that n | 5*K, too. Consequently, n | (5K + 11) - 5K. Now, if n > 1 and n | 11, then n must be eleven.
(and m can be chosen e.g. 9).
Quote: then i tried
gcd(K, 5K+11)....but I'm stuck here.
Could someone direct me to the right path.
- Gerard. |
|
|
| Back to top |
|
| Mensanator |
| Posted: Thu May 01, 2008 5:15 pm |
|
|
|
Guest
|
On May 1, 9:56 pm, Gerard Matthew <calibis...@gmail.com> wrote:
Quote: On May 1, 9:41 pm, William Hale <h...@tulane.edu> wrote:
In article
d38853d2-d3c7-465e-a2f3-f6a8da53d...@m36g2000hse.googlegroups.com>,
Gerard Matthew <calibis...@gmail.com> wrote:
Good Day,
I'm trying to get a heads up on how I should tackle a particular
proof.
Prove an integer n > 1 has the properties that n|(35m + 26) and n|(7m
+ 3) for some integer m. What is n?
I'm trying to go down the route of using the Euclidean Algorithm to
solve this problem;
I think congruence approach would be easier:
35m + 26 = 0 (mod n)
7m + 3 = 0 (mod n)
etc.
however, I am getting stuck. I substituted K for
7m + 3 and said that
n| 5K + 11 and n|K
From n|K, conclude 5*n | 5 * K. Use that fact now with n | 5K + 11.
then i tried
gcd(K, 5K+11)....but I'm stuck here.
Should I assume basedon the gcd(A,B) = gcd(A, B-A) that it would boil
down to the gcd(K,11) and since the prove states for n> 1 that the
only option for the gcd of K and 11 is 1....?
Well, I didn't do it that way (I solved the linear congruences
for an n that gives a non-zero result for each congruence that
must be equal). 11 is the only integer between 2 and 1000000
that has that property.
# Python
from gmpy import divm # linear congruence solver
for n in xrange(2,1000000):
try: ma = divm(-26,35,n) # test if lc is solvable for 35m == -26
(mod n)
except: ma = 0 # it's not, use 0
try: mb = divm(-3,7,n) # test if lc is solvable for 7m == -3
(mod n)
except: mb = 0
if ma and mb: # both must be solveable
if ma==mb: # and equal
print 'n:%3d ma:%3d mb:%3d' % (n,ma,mb)
## n: 11 ma: 9 mb: 9
Quote:
I think you mean you have:
n divides gcd(K, 5K+11).
But, gcd(K, 5K+11) = gcd(K, 5K - K +11) = gcd(K, 4K+11) = etc
by using the fact that gcd(A, B) = gcd(A, B - A).
Could someone direct me to the right path.
- Gerard.- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text - |
|
|
| Back to top |
|
| William Hale |
| Posted: Thu May 01, 2008 9:41 pm |
|
|
|
Guest
|
In article
<d38853d2-d3c7-465e-a2f3-f6a8da53d23c@m36g2000hse.googlegroups.com>,
Gerard Matthew <calibishie@gmail.com> wrote:
Quote: Good Day,
I'm trying to get a heads up on how I should tackle a particular
proof.
Prove an integer n > 1 has the properties that n|(35m + 26) and n|(7m
+ 3) for some integer m. What is n?
I'm trying to go down the route of using the Euclidean Algorithm to
solve this problem;
I think congruence approach would be easier:
35m + 26 = 0 (mod n)
7m + 3 = 0 (mod n)
etc.
Quote: however, I am getting stuck. I substituted K for
7m + 3 and said that
n| 5K + 11 and n|K
From n|K, conclude 5*n | 5 * K. Use that fact now with n | 5K + 11.
Quote:
then i tried
gcd(K, 5K+11)....but I'm stuck here.
I think you mean you have:
n divides gcd(K, 5K+11).
But, gcd(K, 5K+11) = gcd(K, 5K - K +11) = gcd(K, 4K+11) = etc
by using the fact that gcd(A, B) = gcd(A, B - A).
Quote:
Could someone direct me to the right path.
- Gerard. |
|
|
| Back to top |
|
| William Elliot |
| Posted: Thu May 01, 2008 11:42 pm |
|
|
|
Guest
|
On Thu, 1 May 2008, Gerard Matthew wrote:
Quote: Good Day,
I'm trying to get a heads up on how I should tackle a particular
proof.
Prove an integer n > 1 has the properties that n|(35m + 26) and n|(7m
+ 3) for some integer m. What is n?
Huh? That is not a sentence.
Assume n | (35m + 26) and n | (7m + 3). Thus
.. . n | (35m = 15)
.. . n | 11
.. . n = 1 or 11 |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Tue May 13, 2008 11:46 am
|
|
