Dgdrxrt

Sort a list of pairs representing an acyclic, partial automorphism

Semisimplicity of the category of coherent sheaves?

Simulating Exploding Dice

How is simplicity better than precision and clarity in prose?

How to pronounce 1ターン?

What's the point in a preamp?

Did God make two great lights or did He make the great light two?

Can a 1st-level character have an ability score above 18?

What was the last x86 CPU that did not have the x87 floating-point unit built in?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

How do you keep chess fun when your opponent constantly beats you?

Do warforged have souls?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

Match Roman Numerals

How can I protect witches in combat who wear limited clothing?

Can withdrawing asylum be illegal?

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

Can the DM override racial traits?

How does this infinite series simplify to an integral?

He got a vote 80% that of Emmanuel Macron’s

Why did all the guest students take carriages to the Yule Ball?

Why does the Event Horizon Telescope (EHT) not include telescopes from Africa, Asia or Australia?

Single author papers against my advisor's will?

How to split my screen on my Macbook Air?

Question about Modular Arithmetic

1

0

$begingroup$

Let $q$ be an integer number. Consider an integer number $N$ such that $gcd(q-1,N) = 1$.

Question: How to show that if $q^d = 1 pmodN$ for some positive integer $d$, then we get
$$
1 + q + q^2 + cdots + q^(d-1) = 0 pmod N tag1
$$

Try: It follows from ($1$) that
$$
1 + q + q^2 + cdots + q^(d-1)=fracq^d-1q-1
$$

Now the assumption $gcd(q-1,N) = 1$ implies that $q-1neq 0 modN$. Therefore, we get
$$
fracq^d-1q-1=frac1-1q-1=0 pmodN
$$

Is the given proof correct?

Thanks for any suggestions.

discrete-mathematics modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  $text gcd (q-1,N) = ?$
  $endgroup$
  – Dbchatto67
  Mar 31 at 13:17
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Dbchatto67 - $textgcd$ is a very common notation for the greatest common divisor function.
  $endgroup$
  – Paul Sinclair
  Mar 31 at 21:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  No, your proof is inadequate. $q-1 notequiv 0 mod N$ does not necessarily mean you can divide by $q-1$. When $N$ is composite, $Bbb Z_N$ has zero divisors, which do not have inverses, despite not being $0$.
  $endgroup$
  – Paul Sinclair
  Mar 31 at 21:21
  

  
  
  
  

add a comment | 

1

0

$begingroup$

Let $q$ be an integer number. Consider an integer number $N$ such that $gcd(q-1,N) = 1$.

Question: How to show that if $q^d = 1 pmodN$ for some positive integer $d$, then we get
$$
1 + q + q^2 + cdots + q^(d-1) = 0 pmod N tag1
$$

Try: It follows from ($1$) that
$$
1 + q + q^2 + cdots + q^(d-1)=fracq^d-1q-1
$$

Now the assumption $gcd(q-1,N) = 1$ implies that $q-1neq 0 modN$. Therefore, we get
$$
fracq^d-1q-1=frac1-1q-1=0 pmodN
$$

Is the given proof correct?

Thanks for any suggestions.

discrete-mathematics modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  $text gcd (q-1,N) = ?$
  $endgroup$
  – Dbchatto67
  Mar 31 at 13:17
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Dbchatto67 - $textgcd$ is a very common notation for the greatest common divisor function.
  $endgroup$
  – Paul Sinclair
  Mar 31 at 21:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  No, your proof is inadequate. $q-1 notequiv 0 mod N$ does not necessarily mean you can divide by $q-1$. When $N$ is composite, $Bbb Z_N$ has zero divisors, which do not have inverses, despite not being $0$.
  $endgroup$
  – Paul Sinclair
  Mar 31 at 21:21
  

  
  
  
  

add a comment | 

$begingroup$

Let $q$ be an integer number. Consider an integer number $N$ such that $gcd(q-1,N) = 1$.

Question: How to show that if $q^d = 1 pmodN$ for some positive integer $d$, then we get
$$
1 + q + q^2 + cdots + q^(d-1) = 0 pmod N tag1
$$

Try: It follows from ($1$) that
$$
1 + q + q^2 + cdots + q^(d-1)=fracq^d-1q-1
$$

Now the assumption $gcd(q-1,N) = 1$ implies that $q-1neq 0 modN$. Therefore, we get
$$
fracq^d-1q-1=frac1-1q-1=0 pmodN
$$

Is the given proof correct?

Thanks for any suggestions.

discrete-mathematics modular-arithmetic greatest-common-divisor

share|cite|improve this question

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

$endgroup$

share|cite|improve this question

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

share|cite|improve this question

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

edited Mar 31 at 17:53

user0410

324112

edited Mar 31 at 17:53

user0410

324112

asked Mar 31 at 12:44

NightRain23NightRain23

508

asked Mar 31 at 12:44

NightRain23NightRain23

508

1 Answer
1

active

oldest

votes

2

$begingroup$

You almost have it. Note that although it's true $gcd(q-1,N) = 1$ implies that $q-1 notequiv 0 pmodN$, this is not sufficient. For example, if $N = 6 = 2 times 3$, you also need to show that $q - 1 notequiv 2,3,4 pmod 6$.

Given that $q^d equiv 1 pmodN$, this means that

$$q^d - 1 = kN tag1labeleq1$$

for some integer $k$. Since $q - 1 mid q^d - 1$, then $q - 1 mid kN$. Since $gcd(q-1,N) = 1$, this means no factors of $q - 1$ can divide into $N$, so $q - 1 mid k$. Thus,

$$k = left(q-1right)m tag2labeleq2$$

for some integer $m$. I trust you can finish the rest.

If you're familiar with certain number theory, note you can do this somewhat more simply using that given $gcd(q-1,N) = 1$, then $q - 1$ has a multiplicative inverse modulo $N$. Thus, you can go directly from $q^d - 1 equiv 0 pmodN$ to $fracq^d - 1q - 1 equiv 0 pmodN$.

share|cite|improve this answer

edited Mar 31 at 21:00

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  (+) Nice and perfect answer. I like it.
  $endgroup$
  – user0410
  Mar 31 at 22:22
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user0410 I'm glad you liked it. I usually try to give more basic, thorough answers that try to not assume too much about what the user already knows & is familiar with.
  $endgroup$
  – John Omielan
  Mar 31 at 22:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are not just a user, but a good teacher. I appreciate your description.
  $endgroup$
  – user0410
  Mar 31 at 22:31
  

  
  
  
  

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%2f3169353%2fquestion-about-modular-arithmetic%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

You almost have it. Note that although it's true $gcd(q-1,N) = 1$ implies that $q-1 notequiv 0 pmodN$, this is not sufficient. For example, if $N = 6 = 2 times 3$, you also need to show that $q - 1 notequiv 2,3,4 pmod 6$.

Given that $q^d equiv 1 pmodN$, this means that

$$q^d - 1 = kN tag1labeleq1$$

for some integer $k$. Since $q - 1 mid q^d - 1$, then $q - 1 mid kN$. Since $gcd(q-1,N) = 1$, this means no factors of $q - 1$ can divide into $N$, so $q - 1 mid k$. Thus,

$$k = left(q-1right)m tag2labeleq2$$

for some integer $m$. I trust you can finish the rest.

If you're familiar with certain number theory, note you can do this somewhat more simply using that given $gcd(q-1,N) = 1$, then $q - 1$ has a multiplicative inverse modulo $N$. Thus, you can go directly from $q^d - 1 equiv 0 pmodN$ to $fracq^d - 1q - 1 equiv 0 pmodN$.

share|cite|improve this answer

edited Mar 31 at 21:00

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  (+) Nice and perfect answer. I like it.
  $endgroup$
  – user0410
  Mar 31 at 22:22
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user0410 I'm glad you liked it. I usually try to give more basic, thorough answers that try to not assume too much about what the user already knows & is familiar with.
  $endgroup$
  – John Omielan
  Mar 31 at 22:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are not just a user, but a good teacher. I appreciate your description.
  $endgroup$
  – user0410
  Mar 31 at 22:31
  

  
  
  
  

add a comment | 

2

$begingroup$

You almost have it. Note that although it's true $gcd(q-1,N) = 1$ implies that $q-1 notequiv 0 pmodN$, this is not sufficient. For example, if $N = 6 = 2 times 3$, you also need to show that $q - 1 notequiv 2,3,4 pmod 6$.

Given that $q^d equiv 1 pmodN$, this means that

$$q^d - 1 = kN tag1labeleq1$$

for some integer $k$. Since $q - 1 mid q^d - 1$, then $q - 1 mid kN$. Since $gcd(q-1,N) = 1$, this means no factors of $q - 1$ can divide into $N$, so $q - 1 mid k$. Thus,

$$k = left(q-1right)m tag2labeleq2$$

for some integer $m$. I trust you can finish the rest.

If you're familiar with certain number theory, note you can do this somewhat more simply using that given $gcd(q-1,N) = 1$, then $q - 1$ has a multiplicative inverse modulo $N$. Thus, you can go directly from $q^d - 1 equiv 0 pmodN$ to $fracq^d - 1q - 1 equiv 0 pmodN$.

share|cite|improve this answer

edited Mar 31 at 21:00

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  (+) Nice and perfect answer. I like it.
  $endgroup$
  – user0410
  Mar 31 at 22:22
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user0410 I'm glad you liked it. I usually try to give more basic, thorough answers that try to not assume too much about what the user already knows & is familiar with.
  $endgroup$
  – John Omielan
  Mar 31 at 22:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are not just a user, but a good teacher. I appreciate your description.
  $endgroup$
  – user0410
  Mar 31 at 22:31
  

  
  
  
  

add a comment | 

$begingroup$

You almost have it. Note that although it's true $gcd(q-1,N) = 1$ implies that $q-1 notequiv 0 pmodN$, this is not sufficient. For example, if $N = 6 = 2 times 3$, you also need to show that $q - 1 notequiv 2,3,4 pmod 6$.

Given that $q^d equiv 1 pmodN$, this means that

$$q^d - 1 = kN tag1labeleq1$$

for some integer $k$. Since $q - 1 mid q^d - 1$, then $q - 1 mid kN$. Since $gcd(q-1,N) = 1$, this means no factors of $q - 1$ can divide into $N$, so $q - 1 mid k$. Thus,

$$k = left(q-1right)m tag2labeleq2$$

for some integer $m$. I trust you can finish the rest.

If you're familiar with certain number theory, note you can do this somewhat more simply using that given $gcd(q-1,N) = 1$, then $q - 1$ has a multiplicative inverse modulo $N$. Thus, you can go directly from $q^d - 1 equiv 0 pmodN$ to $fracq^d - 1q - 1 equiv 0 pmodN$.

share|cite|improve this answer

edited Mar 31 at 21:00

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

$endgroup$

share|cite|improve this answer

edited Mar 31 at 21:00

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218

answered Mar 31 at 20:54

John OmielanJohn Omielan

4,9692218