Dtjytyk

How do I automatically answer y in bash script?

Using "nakedly" instead of "with nothing on"

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

Stop battery usage [Ubuntu 18]

Statistical model of ligand substitution

Biased dice probability question

Determine whether f is a function, an injection, a surjection

Estimated State payment too big --> money back; + 2018 Tax Reform

How is simplicity better than precision and clarity in prose?

Cold is to Refrigerator as warm is to?

Active filter with series inductor and resistor - do these exist?

What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?

What LEGO pieces have "real-world" functionality?

Replacing HDD with SSD; what about non-APFS/APFS?

Unable to start mainnet node docker container

Limit for e and 1/e

Writing Thesis: Copying from published papers

What can I do if my MacBook isn’t charging but already ran out?

Slither Like a Snake

I'm thinking of a number

Why does tar appear to skip file contents when output file is /dev/null?

How can I make names more distinctive without making them longer?

Unexpected result with right shift after bitwise negation

Fishing simulator

Show that if $m$ in $mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$.

2

1

$begingroup$

Show that if $m$ in $mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$. Also, I have to work in $mathbb{Z}/63 mathbb{Z}^{*}$, thus the group $63$ modulo $mathbb{Z}$ under multiplication.

So in other words, I have to prove $m^{6} equiv 1 (mod 63)$.

I have no idea how to tie the fact that $m$ has $1$ as gcd with $21$ together with working in the $63$ modulo $mathbb{63}$ group. I would really appreciate some hints or suggestions guide me in the right direction.

abstract-algebra group-theory modular-arithmetic

share|cite|improve this question

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

$endgroup$

add a comment | 

2

1

$begingroup$

Show that if $m$ in $mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$. Also, I have to work in $mathbb{Z}/63 mathbb{Z}^{*}$, thus the group $63$ modulo $mathbb{Z}$ under multiplication.

So in other words, I have to prove $m^{6} equiv 1 (mod 63)$.

I have no idea how to tie the fact that $m$ has $1$ as gcd with $21$ together with working in the $63$ modulo $mathbb{63}$ group. I would really appreciate some hints or suggestions guide me in the right direction.

abstract-algebra group-theory modular-arithmetic

share|cite|improve this question

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

$endgroup$

add a comment | 

$begingroup$

Show that if $m$ in $mathbb{Z}$ has greatest common divisor $1$ with $21$, then $m^{6}-1$ is divisible by $63$. Also, I have to work in $mathbb{Z}/63 mathbb{Z}^{*}$, thus the group $63$ modulo $mathbb{Z}$ under multiplication.

So in other words, I have to prove $m^{6} equiv 1 (mod 63)$.

I have no idea how to tie the fact that $m$ has $1$ as gcd with $21$ together with working in the $63$ modulo $mathbb{63}$ group. I would really appreciate some hints or suggestions guide me in the right direction.

abstract-algebra group-theory modular-arithmetic

share|cite|improve this question

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

$endgroup$

share|cite|improve this question

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

share|cite|improve this question

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

asked Mar 23 at 12:13

MathbeginnerMathbeginner

33618

4 Answers
4

active

oldest

votes

1

$begingroup$

The key point is that $21$ and $63$ have the same prime divisors.

Indeed, since $21 = 3 cdot 7$ and $63 = 3^2 cdot 7$, we have
$$
gcd(m,21)=1 iff gcd(m,3)=1=gcd(m,7) iff gcd(m,63)=1
$$
Then Euler's theorem gives
$$m^6equiv 1 bmod 7, quad m^6equiv 1 bmod 9$$
Therefore, $m^6equiv 1 bmod 63$.

share|cite|improve this answer

edited Mar 24 at 11:42

answered Mar 23 at 14:39

lhflhf

168k11172404

$endgroup$

add a comment | 

1

$begingroup$

$(m,7)=1Rightarrow m^{phi(7)}=m^{6}equiv 1 pmod{7}$

and

$begin{cases}
mequiv 1pmod{3}Rightarrow 9|(m-1)(m^2+m+1)(m^3+1)=m^6-1\
mequiv 2 pmod{3} Rightarrow 9|(m^3+1)|(m^6-1)
end{cases}Rightarrow m^6equiv1pmod{9}$

share|cite|improve this answer

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

$endgroup$

add a comment | 

1

$begingroup$

Hint: The fact that $(m,21)=1$ implies, clearly, that $(m,63)=1$. Hence we can use Euler's Theorem, which says that $x^{phi(n)}=1$ mod $n$ for all $n$, and $x$ coprime to $n$. Here, $phi$ is Euler's totient function. Can you proceed further?

share|cite|improve this answer

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Using Eulers totient function, I would say $varphi(63)=varphi(3^{2} cdot 7) = varphi( ( 3^{2}-3^{1}) cdot 7) = varphi(42)$. Substracting $42$ from $63$ gives $21$, thus I could work in $m^{6} equiv 1 (mod 21)$, correct? But I don't see how this makes the problem easier.
  $endgroup$
  – Mathbeginner
  Mar 23 at 13:42
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner there's no need to work mod $21$, Euler's theorem gives you mod $63$, which is exactly what you want. (i.e. use $n=63$ and $x=m$ immediately)
  $endgroup$
  – YiFan
  Mar 23 at 15:18
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But that would be just stating that since we know $m equiv 1 (mod 21)$, this implies $m equiv 1 (mod 63)$ and that would be the end of it. Is that what you are saying?
  $endgroup$
  – Mathbeginner
  Mar 24 at 8:31
  

  
  
  
  

add a comment | 

0

$begingroup$

Carmichael Function $lambda(63)=[lambda(9),lambda(7)]=6$

$(m,21)=1implies (m,7)=(m,3)=1$

share|cite|improve this answer

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Downvoting this seems a bit harsh. Though it may well be beyond the OP's knowledge level, it may help to introduce readers to this handy generalization.
  $endgroup$
  – Bill Dubuque
  Mar 23 at 15:30
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque, Down-voting like up-voting is not controlled here in MSE. Just now received one: math.stackexchange.com/questions/771320/… .Sometimes I try to learn the flaw: math.stackexchange.com/questions/3157905/…
  $endgroup$
  – lab bhattacharjee
  Mar 24 at 6:10
  

  
  
  
  

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%2f3159245%2fshow-that-if-m-in-mathbbz-has-greatest-common-divisor-1-with-21-then%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The key point is that $21$ and $63$ have the same prime divisors.

Indeed, since $21 = 3 cdot 7$ and $63 = 3^2 cdot 7$, we have
$$
gcd(m,21)=1 iff gcd(m,3)=1=gcd(m,7) iff gcd(m,63)=1
$$
Then Euler's theorem gives
$$m^6equiv 1 bmod 7, quad m^6equiv 1 bmod 9$$
Therefore, $m^6equiv 1 bmod 63$.

share|cite|improve this answer

edited Mar 24 at 11:42

answered Mar 23 at 14:39

lhflhf

168k11172404

$endgroup$

add a comment | 

1

$begingroup$

The key point is that $21$ and $63$ have the same prime divisors.

Indeed, since $21 = 3 cdot 7$ and $63 = 3^2 cdot 7$, we have
$$
gcd(m,21)=1 iff gcd(m,3)=1=gcd(m,7) iff gcd(m,63)=1
$$
Then Euler's theorem gives
$$m^6equiv 1 bmod 7, quad m^6equiv 1 bmod 9$$
Therefore, $m^6equiv 1 bmod 63$.

share|cite|improve this answer

edited Mar 24 at 11:42

answered Mar 23 at 14:39

lhflhf

168k11172404

$endgroup$

add a comment | 

$begingroup$

The key point is that $21$ and $63$ have the same prime divisors.

Indeed, since $21 = 3 cdot 7$ and $63 = 3^2 cdot 7$, we have
$$
gcd(m,21)=1 iff gcd(m,3)=1=gcd(m,7) iff gcd(m,63)=1
$$
Then Euler's theorem gives
$$m^6equiv 1 bmod 7, quad m^6equiv 1 bmod 9$$
Therefore, $m^6equiv 1 bmod 63$.

share|cite|improve this answer

edited Mar 24 at 11:42

answered Mar 23 at 14:39

lhflhf

168k11172404

$endgroup$

share|cite|improve this answer

edited Mar 24 at 11:42

answered Mar 23 at 14:39

lhflhf

168k11172404

answered Mar 23 at 14:39

lhflhf

168k11172404

answered Mar 23 at 14:39

lhflhf

168k11172404

1

$begingroup$

$(m,7)=1Rightarrow m^{phi(7)}=m^{6}equiv 1 pmod{7}$

and

$begin{cases}
mequiv 1pmod{3}Rightarrow 9|(m-1)(m^2+m+1)(m^3+1)=m^6-1\
mequiv 2 pmod{3} Rightarrow 9|(m^3+1)|(m^6-1)
end{cases}Rightarrow m^6equiv1pmod{9}$

share|cite|improve this answer

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

$endgroup$

add a comment | 

1

$begingroup$

$(m,7)=1Rightarrow m^{phi(7)}=m^{6}equiv 1 pmod{7}$

and

$begin{cases}
mequiv 1pmod{3}Rightarrow 9|(m-1)(m^2+m+1)(m^3+1)=m^6-1\
mequiv 2 pmod{3} Rightarrow 9|(m^3+1)|(m^6-1)
end{cases}Rightarrow m^6equiv1pmod{9}$

share|cite|improve this answer

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

$endgroup$

add a comment | 

$begingroup$

$(m,7)=1Rightarrow m^{phi(7)}=m^{6}equiv 1 pmod{7}$

and

$begin{cases}
mequiv 1pmod{3}Rightarrow 9|(m-1)(m^2+m+1)(m^3+1)=m^6-1\
mequiv 2 pmod{3} Rightarrow 9|(m^3+1)|(m^6-1)
end{cases}Rightarrow m^6equiv1pmod{9}$

share|cite|improve this answer

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

$endgroup$

share|cite|improve this answer

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

answered Mar 23 at 12:42

giannispapavgiannispapav

2,000325

1

$begingroup$

Hint: The fact that $(m,21)=1$ implies, clearly, that $(m,63)=1$. Hence we can use Euler's Theorem, which says that $x^{phi(n)}=1$ mod $n$ for all $n$, and $x$ coprime to $n$. Here, $phi$ is Euler's totient function. Can you proceed further?

share|cite|improve this answer

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Using Eulers totient function, I would say $varphi(63)=varphi(3^{2} cdot 7) = varphi( ( 3^{2}-3^{1}) cdot 7) = varphi(42)$. Substracting $42$ from $63$ gives $21$, thus I could work in $m^{6} equiv 1 (mod 21)$, correct? But I don't see how this makes the problem easier.
  $endgroup$
  – Mathbeginner
  Mar 23 at 13:42
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner there's no need to work mod $21$, Euler's theorem gives you mod $63$, which is exactly what you want. (i.e. use $n=63$ and $x=m$ immediately)
  $endgroup$
  – YiFan
  Mar 23 at 15:18
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But that would be just stating that since we know $m equiv 1 (mod 21)$, this implies $m equiv 1 (mod 63)$ and that would be the end of it. Is that what you are saying?
  $endgroup$
  – Mathbeginner
  Mar 24 at 8:31
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint: The fact that $(m,21)=1$ implies, clearly, that $(m,63)=1$. Hence we can use Euler's Theorem, which says that $x^{phi(n)}=1$ mod $n$ for all $n$, and $x$ coprime to $n$. Here, $phi$ is Euler's totient function. Can you proceed further?

share|cite|improve this answer

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Using Eulers totient function, I would say $varphi(63)=varphi(3^{2} cdot 7) = varphi( ( 3^{2}-3^{1}) cdot 7) = varphi(42)$. Substracting $42$ from $63$ gives $21$, thus I could work in $m^{6} equiv 1 (mod 21)$, correct? But I don't see how this makes the problem easier.
  $endgroup$
  – Mathbeginner
  Mar 23 at 13:42
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mathbeginner there's no need to work mod $21$, Euler's theorem gives you mod $63$, which is exactly what you want. (i.e. use $n=63$ and $x=m$ immediately)
  $endgroup$
  – YiFan
  Mar 23 at 15:18
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But that would be just stating that since we know $m equiv 1 (mod 21)$, this implies $m equiv 1 (mod 63)$ and that would be the end of it. Is that what you are saying?
  $endgroup$
  – Mathbeginner
  Mar 24 at 8:31
  

  
  
  
  

add a comment | 

$begingroup$

Hint: The fact that $(m,21)=1$ implies, clearly, that $(m,63)=1$. Hence we can use Euler's Theorem, which says that $x^{phi(n)}=1$ mod $n$ for all $n$, and $x$ coprime to $n$. Here, $phi$ is Euler's totient function. Can you proceed further?

share|cite|improve this answer

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

$endgroup$

share|cite|improve this answer

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

answered Mar 23 at 13:09

YiFanYiFan

5,2982728

0

$begingroup$

Carmichael Function $lambda(63)=[lambda(9),lambda(7)]=6$

$(m,21)=1implies (m,7)=(m,3)=1$

share|cite|improve this answer

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Downvoting this seems a bit harsh. Though it may well be beyond the OP's knowledge level, it may help to introduce readers to this handy generalization.
  $endgroup$
  – Bill Dubuque
  Mar 23 at 15:30
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque, Down-voting like up-voting is not controlled here in MSE. Just now received one: math.stackexchange.com/questions/771320/… .Sometimes I try to learn the flaw: math.stackexchange.com/questions/3157905/…
  $endgroup$
  – lab bhattacharjee
  Mar 24 at 6:10
  

  
  
  
  

add a comment | 

0

$begingroup$

Carmichael Function $lambda(63)=[lambda(9),lambda(7)]=6$

$(m,21)=1implies (m,7)=(m,3)=1$

share|cite|improve this answer

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Downvoting this seems a bit harsh. Though it may well be beyond the OP's knowledge level, it may help to introduce readers to this handy generalization.
  $endgroup$
  – Bill Dubuque
  Mar 23 at 15:30
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque, Down-voting like up-voting is not controlled here in MSE. Just now received one: math.stackexchange.com/questions/771320/… .Sometimes I try to learn the flaw: math.stackexchange.com/questions/3157905/…
  $endgroup$
  – lab bhattacharjee
  Mar 24 at 6:10
  

  
  
  
  

add a comment | 

$begingroup$

Carmichael Function $lambda(63)=[lambda(9),lambda(7)]=6$

$(m,21)=1implies (m,7)=(m,3)=1$

share|cite|improve this answer

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

$endgroup$

share|cite|improve this answer

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279

answered Mar 23 at 12:15

lab bhattacharjeelab bhattacharjee

229k15159279