How to compute $gcd(d^large 671! +! 1, d^large 610! −!1), d = gcd(51^large 610! +! 1, 51^large 671! −!1)$ The Next CEO of Stack OverflowShow $(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 problemHow to compute the gcd $(61^610+1,61^671−1)$Is there any relation between GCD and modulo??What 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-5right)$ in $mathbbZ[sqrt-5]$How to compute the gcd $(61^610+1,61^671−1)$
I believe this to be a fraud - hired, then asked to cash check and send cash as Bitcoin
Is a distribution that is normal, but highly skewed considered Gaussian?
How did people program for Consoles with multiple CPUs?
Why is the US ranked as #45 in Press Freedom ratings, despite its extremely permissive free speech laws?
Why do airplanes bank sharply to the right after air-to-air refueling?
Method for adding error messages to a dictionary given a key
What flight has the highest ratio of timezone difference to flight time?
Running a General Election and the European Elections together
If the heap is zero-initialized for security, then why is the stack merely uninitialized?
RigExpert AA-35 - Interpreting The Information
Can we say or write : "No, it'sn't"?
Make solar eclipses exceedingly rare, but still have new moons
Is there a way to save my career from absolute disaster?
Won the lottery - how do I keep the money?
Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?
Where do students learn to solve polynomial equations these days?
Would a completely good Muggle be able to use a wand?
What connection does MS Office have to Netscape Navigator?
Is French Guiana a (hard) EU border?
Can MTA send mail via a relay without being told so?
Rotate a column
Domestic-to-international connection at Orlando (MCO)
The exact meaning of 'Mom made me a sandwich'
How to delete every two lines after 3rd lines in a file contains very large number of lines?
How to compute $gcd(d^large 671! +! 1, d^large 610! −!1), d = gcd(51^large 610! +! 1, 51^large 671! −!1)$
The Next CEO of Stack OverflowShow $(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 problemHow to compute the gcd $(61^610+1,61^671−1)$Is there any relation between GCD and modulo??What 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-5right)$ in $mathbbZ[sqrt-5]$How to compute the gcd $(61^610+1,61^671−1)$
$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
62
$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
62
$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
62
$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
62
edited Mar 22 at 23:40
Bill Dubuque
213k29196654
asked Mar 19 at 12:49
rj123rj123
62
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
62
asked Mar 19 at 12:49
rj123rj123
62
asked Mar 19 at 12:49
rj123rj123
62
62
$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^mpm 1)-(a^m+a^m-1),a+1) = gcd(a^m-1mp 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.6k22891
$endgroup$
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor#90fEuclidean$ algorithm.
$a = 51^large 61Rightarrow, d = (a^large 11-1,,a^large 10+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^large 61Rightarrow,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#90fusing$ $ (x,y) = (x,, ybmod x)$
$beginalign (color#0a0a^large 11!+s,,a^large 10!-s) &= (color#0a0s(color#0a0 a!+!1),, a^large 10!-s) ,rm by bmod a^large 10!-s!:, a^large 10!equiv s,Rightarrow, color#0a0a^large 11!equiv a^large 10a equiv color#0a0sa \[.2em]
&= , (a!+!1, ,color#c00a^large 10!-s) rm by, (s,,a^large 10!-s) = (s,a^large 10)=1, , rm by, (s,a) = 1\[.2em]
&= (a!+!1, color#c001, -, s) rm by bmod a+1!: aequiv -1,Rightarrow, color#c00a^10equiv (-1)^10equivcolor#c00 1 \[.2em]
endalign$
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^610times 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,7051514
$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^mpm 1)-(a^m+a^m-1),a+1) = gcd(a^m-1mp 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.6k22891
$endgroup$
add a comment |
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^mpm 1)-(a^m+a^m-1),a+1) = gcd(a^m-1mp 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.6k22891
$endgroup$
add a comment |
$begingroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^mpm 1)-(a^m+a^m-1),a+1) = gcd(a^m-1mp 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.6k22891
$endgroup$
First note: $gcd(a^m pm 1, a+1)=gcd((a^mpm 1)-(a^m+a^m-1),a+1) = gcd(a^m-1mp 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.6k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.6k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.6k22891
answered Mar 22 at 19:38
fleabloodfleablood
73.6k22891
73.6k22891
add a comment |
add a comment |
$begingroup$
As in the proofs here and here, we reduce to coprime powers then apply the $rmcolor#90fEuclidean$ algorithm.
$a = 51^large 61Rightarrow, d = (a^large 11-1,,a^large 10+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^large 61Rightarrow,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#90fusing$ $ (x,y) = (x,, ybmod x)$
$beginalign (color#0a0a^large 11!+s,,a^large 10!-s) &= (color#0a0s(color#0a0 a!+!1),, a^large 10!-s) ,rm by bmod a^large 10!-s!:, a^large 10!equiv s,Rightarrow, color#0a0a^large 11!equiv a^large 10a equiv color#0a0sa \[.2em]
&= , (a!+!1, ,color#c00a^large 10!-s) rm by, (s,,a^large 10!-s) = (s,a^large 10)=1, , rm by, (s,a) = 1\[.2em]
&= (a!+!1, color#c001, -, s) rm by bmod a+1!: aequiv -1,Rightarrow, color#c00a^10equiv (-1)^10equivcolor#c00 1 \[.2em]
endalign$
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#90fEuclidean$ algorithm.
$a = 51^large 61Rightarrow, d = (a^large 11-1,,a^large 10+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^large 61Rightarrow,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#90fusing$ $ (x,y) = (x,, ybmod x)$
$beginalign (color#0a0a^large 11!+s,,a^large 10!-s) &= (color#0a0s(color#0a0 a!+!1),, a^large 10!-s) ,rm by bmod a^large 10!-s!:, a^large 10!equiv s,Rightarrow, color#0a0a^large 11!equiv a^large 10a equiv color#0a0sa \[.2em]
&= , (a!+!1, ,color#c00a^large 10!-s) rm by, (s,,a^large 10!-s) = (s,a^large 10)=1, , rm by, (s,a) = 1\[.2em]
&= (a!+!1, color#c001, -, s) rm by bmod a+1!: aequiv -1,Rightarrow, color#c00a^10equiv (-1)^10equivcolor#c00 1 \[.2em]
endalign$
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#90fEuclidean$ algorithm.
$a = 51^large 61Rightarrow, d = (a^large 11-1,,a^large 10+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^large 61Rightarrow,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#90fusing$ $ (x,y) = (x,, ybmod x)$
$beginalign (color#0a0a^large 11!+s,,a^large 10!-s) &= (color#0a0s(color#0a0 a!+!1),, a^large 10!-s) ,rm by bmod a^large 10!-s!:, a^large 10!equiv s,Rightarrow, color#0a0a^large 11!equiv a^large 10a equiv color#0a0sa \[.2em]
&= , (a!+!1, ,color#c00a^large 10!-s) rm by, (s,,a^large 10!-s) = (s,a^large 10)=1, , rm by, (s,a) = 1\[.2em]
&= (a!+!1, color#c001, -, s) rm by bmod a+1!: aequiv -1,Rightarrow, color#c00a^10equiv (-1)^10equivcolor#c00 1 \[.2em]
endalign$
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#90fEuclidean$ algorithm.
$a = 51^large 61Rightarrow, d = (a^large 11-1,,a^large 10+1) = (a!+!1,2) = 2,$ by $,bf T1,$ below, with $ s = -1$
$a, =, d^large 61Rightarrow,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#90fusing$ $ (x,y) = (x,, ybmod x)$
$beginalign (color#0a0a^large 11!+s,,a^large 10!-s) &= (color#0a0s(color#0a0 a!+!1),, a^large 10!-s) ,rm by bmod a^large 10!-s!:, a^large 10!equiv s,Rightarrow, color#0a0a^large 11!equiv a^large 10a equiv color#0a0sa \[.2em]
&= , (a!+!1, ,color#c00a^large 10!-s) rm by, (s,,a^large 10!-s) = (s,a^large 10)=1, , rm by, (s,a) = 1\[.2em]
&= (a!+!1, color#c001, -, s) rm by bmod a+1!: aequiv -1,Rightarrow, color#c00a^10equiv (-1)^10equivcolor#c00 1 \[.2em]
endalign$
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^610times 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,7051514
$endgroup$
add a comment |
$begingroup$
$$51^671=51^610times 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,7051514
$endgroup$
add a comment |
$begingroup$
$$51^671=51^610times 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,7051514
$endgroup$
$$51^671=51^610times 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,7051514
edited Mar 24 at 2:50
answered Mar 21 at 19:45
siroussirous
1,7051514
answered Mar 21 at 19:45
siroussirous
1,7051514
answered Mar 21 at 19:45
siroussirous
1,7051514
1,7051514
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