How to compute $gcd(d^{large 671}! +! 1, d^{large 610}! −!1), d = gcd(51^{large 610}! +! 1, 51^{large 671}!...
How is it possible to have an ability score that is less than 3?
What defenses are there against being summoned by the Gate spell?
Replacing matching entries in one column of a file by another column from a different file
Important Resources for Dark Age Civilizations?
Has there ever been an airliner design involving reducing generator load by installing solar panels?
dbcc cleantable batch size explanation
Theorems that impeded progress
Maximum likelihood parameters deviate from posterior distributions
Did Shadowfax go to Valinor?
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
Why do I get two different answers for this counting problem?
RSA: Danger of using p to create q
Arrow those variables!
Rock identification in KY
A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?
What typically incentivizes a professor to change jobs to a lower ranking university?
Are the number of citations and number of published articles the most important criteria for a tenure promotion?
Approximately how much travel time was saved by the opening of the Suez Canal in 1869?
Alternative to sending password over mail?
Do infinite dimensional systems make sense?
How much of data wrangling is a data scientist's job?
Modeling an IP Address
Can a vampire attack twice with their claws using Multiattack?
A case of the sniffles
How to compute $gcd(d^{large 671}! +! 1, d^{large 610}! −!1), d = gcd(51^{large 610}! +! 1, 51^{large 671}! −!1)$
Is there any relation between GCD and modulo??Show $(2^m-1,2^n+1)=1$ if $m$ is oddWhat is $gcd(61^{610}+1,61^{671}-1)$?find $G=gcd(a^m+1,a^n+1)$ from a problemWhat is $gcd(0,0)$?GCD, LCM RelationshipPairs of integers with gcd equal to a given numberUnderstanding the Existence and Uniqueness of the GCDGCD(100!,1.9442173520703009076224 × 10^22)The biggest $gcd(11n+4, 7n+2)$?GCD of two number!GCD and exponentiation of large numbersNo gcd$left(6, 3+3sqrt{-5}right)$ in $mathbb{Z}[sqrt{-5}]$
$begingroup$
Let $(a,b)$ denote the greatest common divisor of $a$ and $b$.
With $ d = (51^{large 610}! + 1,, 51^{large 671}! −1)$
and $ x ,=, (d^{large 671} + 1,, d^{large 610} −1 )$
find $ X = (xbmod 10)$
I used $y=51^{61}$ to reduce $d$ to $d=(y^{10}+1,y^{11}-1) = (y^{10}+1,y+1)$.
What should I do now?
elementary-number-theory greatest-common-divisor
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
$endgroup$
|
show 5 more comments
$begingroup$
Let $(a,b)$ denote the greatest common divisor of $a$ and $b$.
With $ d = (51^{large 610}! + 1,, 51^{large 671}! −1)$
and $ x ,=, (d^{large 671} + 1,, d^{large 610} −1 )$
find $ X = (xbmod 10)$
I used $y=51^{61}$ to reduce $d$ to $d=(y^{10}+1,y^{11}-1) = (y^{10}+1,y+1)$.
What should I do now?
elementary-number-theory greatest-common-divisor
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
$endgroup$
$begingroup$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06
|
show 5 more comments
$begingroup$
Let $(a,b)$ denote the greatest common divisor of $a$ and $b$.
With $ d = (51^{large 610}! + 1,, 51^{large 671}! −1)$
and $ x ,=, (d^{large 671} + 1,, d^{large 610} −1 )$
find $ X = (xbmod 10)$
I used $y=51^{61}$ to reduce $d$ to $d=(y^{10}+1,y^{11}-1) = (y^{10}+1,y+1)$.
What should I do now?
elementary-number-theory greatest-common-divisor
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
$endgroup$
Let $(a,b)$ denote the greatest common divisor of $a$ and $b$.
With $ d = (51^{large 610}! + 1,, 51^{large 671}! −1)$
and $ x ,=, (d^{large 671} + 1,, d^{large 610} −1 )$
find $ X = (xbmod 10)$
I used $y=51^{61}$ to reduce $d$ to $d=(y^{10}+1,y^{11}-1) = (y^{10}+1,y+1)$.
What should I do now?
elementary-number-theory greatest-common-divisor
elementary-number-theory greatest-common-divisor
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
213k29196654
asked Mar 19 at 12:49
rj123rj123
112
asked Mar 19 at 12:49
rj123rj123
112
asked Mar 19 at 12:49
rj123rj123
112
112
$begingroup$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06
|
show 5 more comments
$begingroup$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06
$begingroup$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06
|
show 5 more comments
3 Answers
3
active
oldest
votes
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^{m}pm 1)-(a^{m}+a^{m-1}),a+1) = gcd(a^{m-1}mp 1, a+1)$
And via induction $gcd(a^{m}+1, a+1) = gcd(2, a+1)$ if $m$ is even. $gcd(a^{m} - 1,a+1) =gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).
so if we let $a= 51^{61}$.
Then $gcd(51^{610} + 1, 51^{671} - 1)=$
$gcd(a^{11}-1,a^{10} + 1)=$
$gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$
$gcd(a^{10} + 1, a+ 1) = 2$
...
Let $b = 2^{61}$ and so
$gcd(2^{671}+1, 2^{610} -1)= gcd (b^{11} + 1, b^{10} -1)=$
$gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor{#90f}{Euclidean}$ algorithm.
$a = 51^{large 61}Rightarrow, d = (a^{large 11}-1,,a^{large 10}+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^{large 61}Rightarrow,x = (a^{large 11}+1,,a^{large 10}-1) =, a!+!1 = d^{large 61}!+1 = 2^{large 61}!+1,$ by $,bf T1,,$ $,s = 1$
${bf T1}, (s,a)! =!1, Rightarrow, (a^{large 11}!+s,,a^{large 10}-s), = (a!+!1,,1!-!s). $ Proof: $,rmcolor{#90f}{using}$ $ (x,y) = (x,, ybmod x)$
$begin{align} (color{#0a0}{a^{large 11}}!+s,,{a^{large 10}}!-s) &= (color{#0a0}{s}(color{#0a0} a!+!1),, {a^{large 10}}!-s) ,{rm by} bmod a^{large 10}!-s!:, a^{large 10}!equiv s,Rightarrow, color{#0a0}{a^{large 11}}!equiv a^{large 10}a equiv color{#0a0}{sa} \[.2em]
&= , (a!+!1, ,color{#c00}{a^{large 10}}!-s) {rm by}, (s,,a^{large 10}!-s) = (s,a^{large 10})=1, , {rm by}, (s,a) = 1\[.2em]
&= (a!+!1, color{#c00}1, -, s) {rm by} bmod a+1!: aequiv -1,Rightarrow, color{#c00}{a^{10}}equiv (-1)^{10}equivcolor{#c00} 1 \[.2em]
end{align}$
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
add a comment |
$begingroup$
$$51^{671}=51^{610}times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$
$$(51^{61}, 51^{61}+1)=1$$
So we may write:
$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$
$$51^{61}+1=52 k=2times 26 k$$
$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$
$$(26, 26k_1+1)=1$$
However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:
$$x=(2^{671}+1, 2^{610}-1) $$
$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$
$(2^{61},2^{61}+1)=1$, Therefore:
$$x= 2^{61}+1$$
answered Mar 21 at 19:45
siroussirous
1,7001514
$endgroup$
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%2f3154020%2fhow-to-compute-gcdd-large-671-1-d-large-610-%25e2%2588%2592-1-d-gcd5%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^{m}pm 1)-(a^{m}+a^{m-1}),a+1) = gcd(a^{m-1}mp 1, a+1)$
And via induction $gcd(a^{m}+1, a+1) = gcd(2, a+1)$ if $m$ is even. $gcd(a^{m} - 1,a+1) =gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).
so if we let $a= 51^{61}$.
Then $gcd(51^{610} + 1, 51^{671} - 1)=$
$gcd(a^{11}-1,a^{10} + 1)=$
$gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$
$gcd(a^{10} + 1, a+ 1) = 2$
...
Let $b = 2^{61}$ and so
$gcd(2^{671}+1, 2^{610} -1)= gcd (b^{11} + 1, b^{10} -1)=$
$gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^{m}pm 1)-(a^{m}+a^{m-1}),a+1) = gcd(a^{m-1}mp 1, a+1)$
And via induction $gcd(a^{m}+1, a+1) = gcd(2, a+1)$ if $m$ is even. $gcd(a^{m} - 1,a+1) =gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).
so if we let $a= 51^{61}$.
Then $gcd(51^{610} + 1, 51^{671} - 1)=$
$gcd(a^{11}-1,a^{10} + 1)=$
$gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$
$gcd(a^{10} + 1, a+ 1) = 2$
...
Let $b = 2^{61}$ and so
$gcd(2^{671}+1, 2^{610} -1)= gcd (b^{11} + 1, b^{10} -1)=$
$gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^{m}pm 1)-(a^{m}+a^{m-1}),a+1) = gcd(a^{m-1}mp 1, a+1)$
And via induction $gcd(a^{m}+1, a+1) = gcd(2, a+1)$ if $m$ is even. $gcd(a^{m} - 1,a+1) =gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).
so if we let $a= 51^{61}$.
Then $gcd(51^{610} + 1, 51^{671} - 1)=$
$gcd(a^{11}-1,a^{10} + 1)=$
$gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$
$gcd(a^{10} + 1, a+ 1) = 2$
...
Let $b = 2^{61}$ and so
$gcd(2^{671}+1, 2^{610} -1)= gcd (b^{11} + 1, b^{10} -1)=$
$gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
$endgroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^{m}pm 1)-(a^{m}+a^{m-1}),a+1) = gcd(a^{m-1}mp 1, a+1)$
And via induction $gcd(a^{m}+1, a+1) = gcd(2, a+1)$ if $m$ is even. $gcd(a^{m} - 1,a+1) =gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).
so if we let $a= 51^{61}$.
Then $gcd(51^{610} + 1, 51^{671} - 1)=$
$gcd(a^{11}-1,a^{10} + 1)=$
$gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$
$gcd(a^{10} + 1, a+ 1) = 2$
...
Let $b = 2^{61}$ and so
$gcd(2^{671}+1, 2^{610} -1)= gcd (b^{11} + 1, b^{10} -1)=$
$gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.8k22891
73.8k22891
add a comment |
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor{#90f}{Euclidean}$ algorithm.
$a = 51^{large 61}Rightarrow, d = (a^{large 11}-1,,a^{large 10}+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^{large 61}Rightarrow,x = (a^{large 11}+1,,a^{large 10}-1) =, a!+!1 = d^{large 61}!+1 = 2^{large 61}!+1,$ by $,bf T1,,$ $,s = 1$
${bf T1}, (s,a)! =!1, Rightarrow, (a^{large 11}!+s,,a^{large 10}-s), = (a!+!1,,1!-!s). $ Proof: $,rmcolor{#90f}{using}$ $ (x,y) = (x,, ybmod x)$
$begin{align} (color{#0a0}{a^{large 11}}!+s,,{a^{large 10}}!-s) &= (color{#0a0}{s}(color{#0a0} a!+!1),, {a^{large 10}}!-s) ,{rm by} bmod a^{large 10}!-s!:, a^{large 10}!equiv s,Rightarrow, color{#0a0}{a^{large 11}}!equiv a^{large 10}a equiv color{#0a0}{sa} \[.2em]
&= , (a!+!1, ,color{#c00}{a^{large 10}}!-s) {rm by}, (s,,a^{large 10}!-s) = (s,a^{large 10})=1, , {rm by}, (s,a) = 1\[.2em]
&= (a!+!1, color{#c00}1, -, s) {rm by} bmod a+1!: aequiv -1,Rightarrow, color{#c00}{a^{10}}equiv (-1)^{10}equivcolor{#c00} 1 \[.2em]
end{align}$
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor{#90f}{Euclidean}$ algorithm.
$a = 51^{large 61}Rightarrow, d = (a^{large 11}-1,,a^{large 10}+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^{large 61}Rightarrow,x = (a^{large 11}+1,,a^{large 10}-1) =, a!+!1 = d^{large 61}!+1 = 2^{large 61}!+1,$ by $,bf T1,,$ $,s = 1$
${bf T1}, (s,a)! =!1, Rightarrow, (a^{large 11}!+s,,a^{large 10}-s), = (a!+!1,,1!-!s). $ Proof: $,rmcolor{#90f}{using}$ $ (x,y) = (x,, ybmod x)$
$begin{align} (color{#0a0}{a^{large 11}}!+s,,{a^{large 10}}!-s) &= (color{#0a0}{s}(color{#0a0} a!+!1),, {a^{large 10}}!-s) ,{rm by} bmod a^{large 10}!-s!:, a^{large 10}!equiv s,Rightarrow, color{#0a0}{a^{large 11}}!equiv a^{large 10}a equiv color{#0a0}{sa} \[.2em]
&= , (a!+!1, ,color{#c00}{a^{large 10}}!-s) {rm by}, (s,,a^{large 10}!-s) = (s,a^{large 10})=1, , {rm by}, (s,a) = 1\[.2em]
&= (a!+!1, color{#c00}1, -, s) {rm by} bmod a+1!: aequiv -1,Rightarrow, color{#c00}{a^{10}}equiv (-1)^{10}equivcolor{#c00} 1 \[.2em]
end{align}$
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor{#90f}{Euclidean}$ algorithm.
$a = 51^{large 61}Rightarrow, d = (a^{large 11}-1,,a^{large 10}+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^{large 61}Rightarrow,x = (a^{large 11}+1,,a^{large 10}-1) =, a!+!1 = d^{large 61}!+1 = 2^{large 61}!+1,$ by $,bf T1,,$ $,s = 1$
${bf T1}, (s,a)! =!1, Rightarrow, (a^{large 11}!+s,,a^{large 10}-s), = (a!+!1,,1!-!s). $ Proof: $,rmcolor{#90f}{using}$ $ (x,y) = (x,, ybmod x)$
$begin{align} (color{#0a0}{a^{large 11}}!+s,,{a^{large 10}}!-s) &= (color{#0a0}{s}(color{#0a0} a!+!1),, {a^{large 10}}!-s) ,{rm by} bmod a^{large 10}!-s!:, a^{large 10}!equiv s,Rightarrow, color{#0a0}{a^{large 11}}!equiv a^{large 10}a equiv color{#0a0}{sa} \[.2em]
&= , (a!+!1, ,color{#c00}{a^{large 10}}!-s) {rm by}, (s,,a^{large 10}!-s) = (s,a^{large 10})=1, , {rm by}, (s,a) = 1\[.2em]
&= (a!+!1, color{#c00}1, -, s) {rm by} bmod a+1!: aequiv -1,Rightarrow, color{#c00}{a^{10}}equiv (-1)^{10}equivcolor{#c00} 1 \[.2em]
end{align}$
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor{#90f}{Euclidean}$ algorithm.
$a = 51^{large 61}Rightarrow, d = (a^{large 11}-1,,a^{large 10}+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^{large 61}Rightarrow,x = (a^{large 11}+1,,a^{large 10}-1) =, a!+!1 = d^{large 61}!+1 = 2^{large 61}!+1,$ by $,bf T1,,$ $,s = 1$
${bf T1}, (s,a)! =!1, Rightarrow, (a^{large 11}!+s,,a^{large 10}-s), = (a!+!1,,1!-!s). $ Proof: $,rmcolor{#90f}{using}$ $ (x,y) = (x,, ybmod x)$
$begin{align} (color{#0a0}{a^{large 11}}!+s,,{a^{large 10}}!-s) &= (color{#0a0}{s}(color{#0a0} a!+!1),, {a^{large 10}}!-s) ,{rm by} bmod a^{large 10}!-s!:, a^{large 10}!equiv s,Rightarrow, color{#0a0}{a^{large 11}}!equiv a^{large 10}a equiv color{#0a0}{sa} \[.2em]
&= , (a!+!1, ,color{#c00}{a^{large 10}}!-s) {rm by}, (s,,a^{large 10}!-s) = (s,a^{large 10})=1, , {rm by}, (s,a) = 1\[.2em]
&= (a!+!1, color{#c00}1, -, s) {rm by} bmod a+1!: aequiv -1,Rightarrow, color{#c00}{a^{10}}equiv (-1)^{10}equivcolor{#c00} 1 \[.2em]
end{align}$
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
edited Mar 23 at 18:57
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
answered Mar 19 at 14:41
Bill DubuqueBill Dubuque
213k29196654
213k29196654
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
add a comment |
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
$begingroup$
Thus $,X = (2^{large 61}!+1bmod 10) = 3, $ by $ 2^{large 61}! bmod 10 = 2big((2^{large 4})^{large 15} bmod 5big) = 2 $
$endgroup$
– Bill Dubuque
Mar 22 at 23:29
add a comment |
$begingroup$
$$51^{671}=51^{610}times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$
$$(51^{61}, 51^{61}+1)=1$$
So we may write:
$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$
$$51^{61}+1=52 k=2times 26 k$$
$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$
$$(26, 26k_1+1)=1$$
However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:
$$x=(2^{671}+1, 2^{610}-1) $$
$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$
$(2^{61},2^{61}+1)=1$, Therefore:
$$x= 2^{61}+1$$
answered Mar 21 at 19:45
siroussirous
1,7001514
$endgroup$
add a comment |
$begingroup$
$$51^{671}=51^{610}times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$
$$(51^{61}, 51^{61}+1)=1$$
So we may write:
$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$
$$51^{61}+1=52 k=2times 26 k$$
$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$
$$(26, 26k_1+1)=1$$
However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:
$$x=(2^{671}+1, 2^{610}-1) $$
$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$
$(2^{61},2^{61}+1)=1$, Therefore:
$$x= 2^{61}+1$$
answered Mar 21 at 19:45
siroussirous
1,7001514
$endgroup$
add a comment |
$begingroup$
$$51^{671}=51^{610}times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$
$$(51^{61}, 51^{61}+1)=1$$
So we may write:
$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$
$$51^{61}+1=52 k=2times 26 k$$
$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$
$$(26, 26k_1+1)=1$$
However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:
$$x=(2^{671}+1, 2^{610}-1) $$
$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$
$(2^{61},2^{61}+1)=1$, Therefore:
$$x= 2^{61}+1$$
answered Mar 21 at 19:45
siroussirous
1,7001514
$endgroup$
$$51^{671}=51^{610}times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$
$$(51^{61}, 51^{61}+1)=1$$
So we may write:
$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$
$$51^{61}+1=52 k=2times 26 k$$
$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$
$$(26, 26k_1+1)=1$$
However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:
$$x=(2^{671}+1, 2^{610}-1) $$
$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$
$(2^{61},2^{61}+1)=1$, Therefore:
$$x= 2^{61}+1$$
answered Mar 21 at 19:45
siroussirous
1,7001514
edited Mar 24 at 2:50
answered Mar 21 at 19:45
siroussirous
1,7001514
answered Mar 21 at 19:45
siroussirous
1,7001514
answered Mar 21 at 19:45
siroussirous
1,7001514
1,7001514
add a comment |
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%2f3154020%2fhow-to-compute-gcdd-large-671-1-d-large-610-%25e2%2588%2592-1-d-gcd5%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$
Were you previously taught any method to find gcds of the form $,(a^j+1,a^k-1)$? Does "trick" mean a method of computing said gcd $!bmod 10$ that is (much) simpler than computing the gcd then reducing it $bmod 10$?
$endgroup$
– Bill Dubuque
Mar 19 at 15:54
$begingroup$
As a further hint, note that if $ y=x^{61} $, then $ x^{610}+1= y^{10}+1 $ and $ x^{671}-1=y^{11}-1 $.
$endgroup$
– lonza leggiera
Mar 19 at 16:09
$begingroup$
The reduction to the case of coprime exponents in the prior comment of @Ionza works generally, e.g. see this answer. We can handle this problem in a very similar manner as I do there. See also this answer.
$endgroup$
– Bill Dubuque
Mar 20 at 0:27
$begingroup$
Yeah i want to know the method for computing $(a^{j}+1,a^{k}-1)$ I mean how to derive this formula @BillDubuque
$endgroup$
– rj123
Mar 21 at 9:55
$begingroup$
And I do need to find d at first @BillDubuque
$endgroup$
– rj123
Mar 21 at 10:06