Mixing
Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289
$begingroup$
Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289.
Not got any clue. Please help.
elementary-number-theory
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
$endgroup$
add a comment |
$begingroup$
Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289.
Not got any clue. Please help.
elementary-number-theory
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
$endgroup$
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56
add a comment |
$begingroup$
Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289.
Not got any clue. Please help.
elementary-number-theory
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
$endgroup$
Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289.
Not got any clue. Please help.
elementary-number-theory
elementary-number-theory
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
asked Nov 30 '13 at 10:47
user2369284user2369284
1,403927
1,403927
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56
add a comment |
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.
Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"
$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$
must be a perfect square.
Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.
But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.
edited Jan 8 at 7:11
Yellow
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
$endgroup$
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
add a comment |
$begingroup$
$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
$endgroup$
add a comment |
$begingroup$
Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.
What you are asked to show is the same thing as showing
$$ a^2 -3a - 19 equiv 0 bmod 289 $$
has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:
$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$
where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)
To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.
So first, we need
$$ sqrt{85} = sqrt{0} = 0 mod{17}$$
Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.
However,
$$ (17c)^2 = 289c^2 = 0 mod{289} $$
therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
$endgroup$
add a comment |
$begingroup$
As $289=17^2,$ let us check the divisibility by $17$
$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$
$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$
$$iff(2a-3)^2equiv0$$
$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$
So, $a=17c+10$ where $c$ is some integer
$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
|
show 1 more comment
$begingroup$
Inspired by mercio
let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$
$$a^2-3a-19=(a-10)(a+7)+51$$
As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$
Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$
So, $17^2|(a-10)(a+7),$ but $17^2not|51$
Generalization:
Let us find integer $x,y$ such that
$displaystyle x-y=-3$(the coefficient of $a$)
and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$
$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$
$implies x=17d+7$ and $y=x+3=17d+10$
Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$
$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$
$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$
Now the logic is exactly same as the one above
In the above method $d=0$
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f586666%2fprove-that-there-is-no-integer-a-for-which-a2-3a-19-is-divisible-by-289%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.
Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"
$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$
must be a perfect square.
Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.
But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.
edited Jan 8 at 7:11
Yellow
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
$endgroup$
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
add a comment |
$begingroup$
Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.
Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"
$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$
must be a perfect square.
Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.
But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.
edited Jan 8 at 7:11
Yellow
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
$endgroup$
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
add a comment |
$begingroup$
Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.
Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"
$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$
must be a perfect square.
Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.
But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.
edited Jan 8 at 7:11
Yellow
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
$endgroup$
Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.
Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"
$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$
must be a perfect square.
Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.
But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.
edited Jan 8 at 7:11
Yellow
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
edited Jan 8 at 7:11
Yellow
16011
edited Jan 8 at 7:11
Yellow
16011
edited Jan 8 at 7:11
Yellow
16011
16011
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
answered Nov 30 '13 at 11:29
DeepSeaDeepSea
71.2k54487
71.2k54487
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
add a comment |
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
$begingroup$
great answer!!!
$endgroup$
– user2369284
Nov 30 '13 at 11:38
1
1
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
$begingroup$
The expression that must be a perfect square is $17(5+4*17n)$, not $17(5+4*289n)$. It doesn't affect the argument, though.
$endgroup$
– Barry Cipra
Nov 30 '13 at 12:38
add a comment |
$begingroup$
$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
$endgroup$
add a comment |
$begingroup$
$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
$endgroup$
add a comment |
$begingroup$
$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
$endgroup$
$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
answered Nov 30 '13 at 11:07
merciomercio
44.6k257110
44.6k257110
add a comment |
add a comment |
$begingroup$
Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.
What you are asked to show is the same thing as showing
$$ a^2 -3a - 19 equiv 0 bmod 289 $$
has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:
$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$
where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)
To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.
So first, we need
$$ sqrt{85} = sqrt{0} = 0 mod{17}$$
Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.
However,
$$ (17c)^2 = 289c^2 = 0 mod{289} $$
therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
$endgroup$
add a comment |
$begingroup$
Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.
What you are asked to show is the same thing as showing
$$ a^2 -3a - 19 equiv 0 bmod 289 $$
has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:
$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$
where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)
To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.
So first, we need
$$ sqrt{85} = sqrt{0} = 0 mod{17}$$
Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.
However,
$$ (17c)^2 = 289c^2 = 0 mod{289} $$
therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
$endgroup$
add a comment |
$begingroup$
Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.
What you are asked to show is the same thing as showing
$$ a^2 -3a - 19 equiv 0 bmod 289 $$
has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:
$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$
where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)
To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.
So first, we need
$$ sqrt{85} = sqrt{0} = 0 mod{17}$$
Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.
However,
$$ (17c)^2 = 289c^2 = 0 mod{289} $$
therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
$endgroup$
Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.
What you are asked to show is the same thing as showing
$$ a^2 -3a - 19 equiv 0 bmod 289 $$
has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:
$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$
where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)
To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.
So first, we need
$$ sqrt{85} = sqrt{0} = 0 mod{17}$$
Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.
However,
$$ (17c)^2 = 289c^2 = 0 mod{289} $$
therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
edited Nov 20 '15 at 3:08
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
answered Nov 30 '13 at 15:03
HurkylHurkyl
111k9119262
111k9119262
add a comment |
add a comment |
$begingroup$
As $289=17^2,$ let us check the divisibility by $17$
$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$
$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$
$$iff(2a-3)^2equiv0$$
$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$
So, $a=17c+10$ where $c$ is some integer
$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
|
show 1 more comment
$begingroup$
As $289=17^2,$ let us check the divisibility by $17$
$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$
$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$
$$iff(2a-3)^2equiv0$$
$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$
So, $a=17c+10$ where $c$ is some integer
$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
|
show 1 more comment
$begingroup$
As $289=17^2,$ let us check the divisibility by $17$
$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$
$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$
$$iff(2a-3)^2equiv0$$
$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$
So, $a=17c+10$ where $c$ is some integer
$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
As $289=17^2,$ let us check the divisibility by $17$
$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$
$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$
$$iff(2a-3)^2equiv0$$
$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$
So, $a=17c+10$ where $c$ is some integer
$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
answered Nov 30 '13 at 11:03
lab bhattacharjeelab bhattacharjee
225k15157275
225k15157275
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
|
show 1 more comment
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
Initially , have you taken the expression to be divisible by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 11:16
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
@user2369284, yes, I have solved for modulo $17$ as it is a factor of $289$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:18
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
but how can you take so when it is not given ?
$endgroup$
– user2369284
Nov 30 '13 at 11:19
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284, do you know, if $a$ divides $b$ and $b$ divides $c;a$ must divide $c$. Btw, you can check other answers
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:20
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
$begingroup$
@user2369284: No, you don't have to start by solving modulo $17$. However, the arithmetic involved is sometimes simpler if you solve modulo 17, then lift the solution to modulo 289 (e.g. this is often done to calculate square roots). IMO, you shouldn't think about divisibility at all: you should be thinking about modular arithmetic. But if you insist, you know that something divisible by 289 must also be divisible by 17, so it's fair to start there.
$endgroup$
– Hurkyl
Nov 30 '13 at 14:54
|
show 1 more comment
$begingroup$
Inspired by mercio
let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$
$$a^2-3a-19=(a-10)(a+7)+51$$
As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$
Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$
So, $17^2|(a-10)(a+7),$ but $17^2not|51$
Generalization:
Let us find integer $x,y$ such that
$displaystyle x-y=-3$(the coefficient of $a$)
and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$
$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$
$implies x=17d+7$ and $y=x+3=17d+10$
Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$
$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$
$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$
Now the logic is exactly same as the one above
In the above method $d=0$
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
add a comment |
$begingroup$
Inspired by mercio
let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$
$$a^2-3a-19=(a-10)(a+7)+51$$
As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$
Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$
So, $17^2|(a-10)(a+7),$ but $17^2not|51$
Generalization:
Let us find integer $x,y$ such that
$displaystyle x-y=-3$(the coefficient of $a$)
and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$
$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$
$implies x=17d+7$ and $y=x+3=17d+10$
Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$
$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$
$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$
Now the logic is exactly same as the one above
In the above method $d=0$
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
add a comment |
$begingroup$
Inspired by mercio
let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$
$$a^2-3a-19=(a-10)(a+7)+51$$
As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$
Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$
So, $17^2|(a-10)(a+7),$ but $17^2not|51$
Generalization:
Let us find integer $x,y$ such that
$displaystyle x-y=-3$(the coefficient of $a$)
and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$
$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$
$implies x=17d+7$ and $y=x+3=17d+10$
Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$
$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$
$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$
Now the logic is exactly same as the one above
In the above method $d=0$
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
$endgroup$
Inspired by mercio
let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$
$$a^2-3a-19=(a-10)(a+7)+51$$
As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$
Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$
So, $17^2|(a-10)(a+7),$ but $17^2not|51$
Generalization:
Let us find integer $x,y$ such that
$displaystyle x-y=-3$(the coefficient of $a$)
and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$
$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$
$implies x=17d+7$ and $y=x+3=17d+10$
Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$
$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$
$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$
Now the logic is exactly same as the one above
In the above method $d=0$
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
edited Nov 30 '13 at 15:19
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
answered Nov 30 '13 at 11:10
lab bhattacharjeelab bhattacharjee
225k15157275
225k15157275
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
add a comment |
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
why have you taken x-y=3, x+y=17,how did you feel that it was necesary ?
$endgroup$
– user2369284
Nov 30 '13 at 11:23
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, observe the coefficient of $3$ and we need modulo $17$ first. So that both or none of $a-x,a+y$ be divisible by $17$. See this(math.stackexchange.com/questions/9431/…)
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 11:27
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
$begingroup$
@user2369284, please have a look into the edited version
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 15:52
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f586666%2fprove-that-there-is-no-integer-a-for-which-a2-3a-19-is-divisible-by-289%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
HINT: Check divisibility by $17$
$endgroup$
– lab bhattacharjee
Nov 30 '13 at 10:55
$begingroup$
And how to check divisibility by 17 ?
$endgroup$
– user2369284
Nov 30 '13 at 10:56