Fdtxjr

Multi tool use

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$

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

modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

$endgroup$

add a comment | 

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

modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

$endgroup$

add a comment | 

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

modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

$endgroup$

share|cite|improve this question

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

share|cite|improve this question

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

edited Sep 21 '16 at 14:25

user133281

13.7k22752

edited Sep 21 '16 at 14:25

user133281

13.7k22752

asked Sep 21 '16 at 11:34

user1161user1161

271214

asked Sep 21 '16 at 11:34

user1161user1161

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

edited Sep 21 '16 at 14:23

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

$endgroup$

add a comment | 

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

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

$endgroup$

add a comment | 

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

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

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

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

edited Sep 21 '16 at 14:23

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

$endgroup$

add a comment | 

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

edited Sep 21 '16 at 14:23

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

$endgroup$

add a comment | 

$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

edited Sep 21 '16 at 14:23

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

$endgroup$

share|cite|improve this answer

edited Sep 21 '16 at 14:23

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

answered Sep 21 '16 at 13:37

user133281user133281

13.7k22752

answered Sep 21 '16 at 13:37

user133281user133281

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

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

$endgroup$

add a comment | 

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

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

$endgroup$

add a comment | 

$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

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

$endgroup$

share|cite|improve this answer

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

edited Mar 26 at 6:26

Pang

14916

edited Mar 26 at 6:26

Pang

14916

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138

answered Sep 21 '16 at 12:50

ToucanNapoleonToucanNapoleon

40138