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}]$













2












$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?










share|cite|improve this question











$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
















2












$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?










share|cite|improve this question











$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














2












2








2


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?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Mar 22 at 23:40









Bill Dubuque

213k29196654




213k29196654










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


















  • $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










3 Answers
3






active

oldest

votes


















0












$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$






share|cite|improve this answer









$endgroup$





















    0












    $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}$






    share|cite|improve this answer











    $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



















    0












    $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$$






    share|cite|improve this answer











    $endgroup$














      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
      });


      }
      });














      draft saved

      draft discarded


















      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









      0












      $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$






      share|cite|improve this answer









      $endgroup$


















        0












        $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$






        share|cite|improve this answer









        $endgroup$
















          0












          0








          0





          $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$






          share|cite|improve this answer









          $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$







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 22 at 19:38









          fleabloodfleablood

          73.8k22891




          73.8k22891























              0












              $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}$






              share|cite|improve this answer











              $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
















              0












              $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}$






              share|cite|improve this answer











              $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














              0












              0








              0





              $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}$






              share|cite|improve this answer











              $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}$







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited Mar 23 at 18:57

























              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


















              • $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











              0












              $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$$






              share|cite|improve this answer











              $endgroup$


















                0












                $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$$






                share|cite|improve this answer











                $endgroup$
















                  0












                  0








                  0





                  $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$$






                  share|cite|improve this answer











                  $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$$







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Mar 24 at 2:50

























                  answered Mar 21 at 19:45









                  siroussirous

                  1,7001514




                  1,7001514






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Nidaros erkebispedøme

                      Birsay

                      Was Woodrow Wilson really a Liberal?Was World War I a war of liberals against authoritarians?Founding Fathers...