If $gcd(n,q_1)=1$ then show that $gcd(n+tq_1,q)=1$ for some $t$ Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Find the lowest degree of the polynom $P$?Show that $(a) + (b)= R$ for $gcd(a,b) = 1$Show that if a|c, b|c and gcd(a,b)=1, then ab|cIf $gcd(a,b) mid c$, then $gcd(F_a, F_b) mid F_c$, where $F_n$ is the nth fibonacci numberPrime factorisation: Show that if $(a | (b cdot c) text and textgcd(a,c) = 1) Rightarrow a|b$Show: $gcd(a,b)=gcd(a,c)=1impliesgcd(a,bc)=1$Show that if $gcd(b,c)=1$ then $gcd(a,bc) = gcd(a,b)cdot gcd(a,c)$show that if gcd(b,c) = 1 , gcd(a,bc) = gcd(a,b)gcd(a,c)Modular arithmetic for negative numbers proofCalculating Bezout coefficients and gcd for two numbers that divide evenly with no remainder.

Dominant seventh chord in the major scale contains diminished triad of the seventh?

Do I really need recursive chmod to restrict access to a folder?

Why aren't air breathing engines used as small first stages

Check which numbers satisfy the condition [A*B*C = A! + B! + C!]

Is the address of a local variable a constexpr?

What is the longest distance a 13th-level monk can jump while attacking on the same turn?

Can inflation occur in a positive-sum game currency system such as the Stack Exchange reputation system?

I need to find the potential function of a vector field.

Is there a concise way to say "all of the X, one of each"?

Bonus calculation: Am I making a mountain out of a molehill?

"Seemed to had" is it correct?

What does the "x" in "x86" represent?

How discoverable are IPv6 addresses and AAAA names by potential attackers?

How to bypass password on Windows XP account?

Should I call the interviewer directly, if HR aren't responding?

Proof involving the spectral radius and the Jordan canonical form

How to do this path/lattice with tikz

Letter Boxed validator

When is phishing education going too far?

How can players work together to take actions that are otherwise impossible?

If 'B is more likely given A', then 'A is more likely given B'

Why are there no cargo aircraft with "flying wing" design?

Why is there no army of Iron-Mans in the MCU?

What do you call a plan that's an alternative plan in case your initial plan fails?



If $gcd(n,q_1)=1$ then show that $gcd(n+tq_1,q)=1$ for some $t$



Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Find the lowest degree of the polynom $P$?Show that $(a) + (b)= R$ for $gcd(a,b) = 1$Show that if a|c, b|c and gcd(a,b)=1, then ab|cIf $gcd(a,b) mid c$, then $gcd(F_a, F_b) mid F_c$, where $F_n$ is the nth fibonacci numberPrime factorisation: Show that if $(a | (b cdot c) text and textgcd(a,c) = 1) Rightarrow a|b$Show: $gcd(a,b)=gcd(a,c)=1impliesgcd(a,bc)=1$Show that if $gcd(b,c)=1$ then $gcd(a,bc) = gcd(a,b)cdot gcd(a,c)$show that if gcd(b,c) = 1 , gcd(a,bc) = gcd(a,b)gcd(a,c)Modular arithmetic for negative numbers proofCalculating Bezout coefficients and gcd for two numbers that divide evenly with no remainder.










1












$begingroup$



If $q=q_1cdot q_2$ and $(q,n)=a$ and $(n,q_1)=1$ then how to select $t$ s.t. $(n+tq_1,q)=1$




bezout implies that $exists r,s$ s.t. $rn+sq_1=1$ and this means $(rn+sq_1,q)=1$ but how to get rid of $r$ ?










share|cite|improve this question











$endgroup$
















    1












    $begingroup$



    If $q=q_1cdot q_2$ and $(q,n)=a$ and $(n,q_1)=1$ then how to select $t$ s.t. $(n+tq_1,q)=1$




    bezout implies that $exists r,s$ s.t. $rn+sq_1=1$ and this means $(rn+sq_1,q)=1$ but how to get rid of $r$ ?










    share|cite|improve this question











    $endgroup$














      1












      1








      1





      $begingroup$



      If $q=q_1cdot q_2$ and $(q,n)=a$ and $(n,q_1)=1$ then how to select $t$ s.t. $(n+tq_1,q)=1$




      bezout implies that $exists r,s$ s.t. $rn+sq_1=1$ and this means $(rn+sq_1,q)=1$ but how to get rid of $r$ ?










      share|cite|improve this question











      $endgroup$





      If $q=q_1cdot q_2$ and $(q,n)=a$ and $(n,q_1)=1$ then how to select $t$ s.t. $(n+tq_1,q)=1$




      bezout implies that $exists r,s$ s.t. $rn+sq_1=1$ and this means $(rn+sq_1,q)=1$ but how to get rid of $r$ ?







      modular-arithmetic greatest-common-divisor






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Sep 21 '16 at 14:25









      user133281

      13.7k22752




      13.7k22752










      asked Sep 21 '16 at 11:34









      user1161user1161

      271214




      271214




















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.



          We show that this works. Consider a prime $p$ dividing $q$.



          • If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.

          • If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

          In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $gcd(q,n+tq_1)=1$ for this choice of $t$.






          share|cite|improve this answer











          $endgroup$




















            2












            $begingroup$

            While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.



            It states that the sequence $ n + t q_1 _t in mathbbN$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.






            share|cite|improve this answer











            $endgroup$













              Your Answer








              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%2f1935542%2fif-gcdn-q-1-1-then-show-that-gcdntq-1-q-1-for-some-t%23new-answer', 'question_page');

              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              2












              $begingroup$

              An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.



              We show that this works. Consider a prime $p$ dividing $q$.



              • If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.

              • If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

              In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $gcd(q,n+tq_1)=1$ for this choice of $t$.






              share|cite|improve this answer











              $endgroup$

















                2












                $begingroup$

                An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.



                We show that this works. Consider a prime $p$ dividing $q$.



                • If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.

                • If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

                In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $gcd(q,n+tq_1)=1$ for this choice of $t$.






                share|cite|improve this answer











                $endgroup$















                  2












                  2








                  2





                  $begingroup$

                  An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.



                  We show that this works. Consider a prime $p$ dividing $q$.



                  • If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.

                  • If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

                  In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $gcd(q,n+tq_1)=1$ for this choice of $t$.






                  share|cite|improve this answer











                  $endgroup$



                  An explicit construction: take $t$ to be the product of those primes that divide $q$ but not $n$.



                  We show that this works. Consider a prime $p$ dividing $q$.



                  • If $p$ divides $n$ then $p$ does not divide $t$ (by our choice of $t$) or $q_1$ (by $gcd(n,q_1)=1$). Hence $p$ does not divide $n+tq_1$.

                  • If $p$ does not divide $n$ then $p$ divides $t$, so $p$ does not divide $n+tq_1$.

                  In conclusion, no prime $p$ dividing $q$ can divide $n+tq_1$, so $gcd(q,n+tq_1)=1$ for this choice of $t$.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Sep 21 '16 at 14:23

























                  answered Sep 21 '16 at 13:37









                  user133281user133281

                  13.7k22752




                  13.7k22752





















                      2












                      $begingroup$

                      While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.



                      It states that the sequence $ n + t q_1 _t in mathbbN$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.






                      share|cite|improve this answer











                      $endgroup$

















                        2












                        $begingroup$

                        While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.



                        It states that the sequence $ n + t q_1 _t in mathbbN$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.






                        share|cite|improve this answer











                        $endgroup$















                          2












                          2








                          2





                          $begingroup$

                          While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.



                          It states that the sequence $ n + t q_1 _t in mathbbN$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.






                          share|cite|improve this answer











                          $endgroup$



                          While I do not have a direct formula for $t$, we can prove that it exists. However, it is a "bulldozer" argument that uses Dirichlet's Theorem.



                          It states that the sequence $ n + t q_1 _t in mathbbN$ contains infinitely many primes. Hence, all we have to do is choose a $t$ such that $n + t q_1$ is a prime larger than $q$, and we are done.







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Mar 26 at 6:26









                          Pang

                          14916




                          14916










                          answered Sep 21 '16 at 12:50









                          ToucanNapoleonToucanNapoleon

                          40138




                          40138



























                              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%2f1935542%2fif-gcdn-q-1-1-then-show-that-gcdntq-1-q-1-for-some-t%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

                              How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

                              random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

                              Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye