Fdtxjr

Why did the Falcon Heavy center core fall off the ASDS OCISLY barge?

Output the ŋarâþ crîþ alphabet song without using (m)any letters

Short Story with Cinderella as a Voo-doo Witch

Apollo command module space walk?

3 doors, three guards, one stone

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

2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?

What is Arya's weapon design?

How to find all the available tools in mac terminal?

Error "illegal generic type for instanceof" when using local classes

51k Euros annually for a family of 4 in Berlin: Is it enough?

Using et al. for a last / senior author rather than for a first author

Should I use a zero-interest credit card for a large one-time purchase?

Compare a given version number in the form major.minor.build.patch and see if one is less than the other

Can a non-EU citizen traveling with me come with me through the EU passport line?

How does debian/ubuntu knows a package has a updated version

Bete Noir -- no dairy

How to call a function with default parameter through a pointer to function that is the return of another function?

Generate an RGB colour grid

How do pianists reach extremely loud dynamics?

Seeking colloquialism for “just because”

String `!23` is replaced with `docker` in command line

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

How do I stop a creek from eroding my steep embankment?

How to find an element of order 30 in the multiplicative group of $Bbb Z_900$?

0

1

$begingroup$

I need to find at least one element which has order $30$ in the multiplicative group of $Bbb Z_900$. I'm following this approach but not really understood how to apply correctly the CRT to set the three congruences. In particular, I don't understand why the order of a is a divisor of 2 etc. Can anyone explain me better how to apply the CRT to this problem? Thank you.

abstract-algebra discrete-mathematics ring-theory chinese-remainder-theorem

share|cite|improve this question

asked Mar 26 at 18:01

JackJack

1047

$endgroup$

add a comment | 

0

1

$begingroup$

I need to find at least one element which has order $30$ in the multiplicative group of $Bbb Z_900$. I'm following this approach but not really understood how to apply correctly the CRT to set the three congruences. In particular, I don't understand why the order of a is a divisor of 2 etc. Can anyone explain me better how to apply the CRT to this problem? Thank you.

abstract-algebra discrete-mathematics ring-theory chinese-remainder-theorem

share|cite|improve this question

asked Mar 26 at 18:01

JackJack

1047

$endgroup$

add a comment | 

$begingroup$

I need to find at least one element which has order $30$ in the multiplicative group of $Bbb Z_900$. I'm following this approach but not really understood how to apply correctly the CRT to set the three congruences. In particular, I don't understand why the order of a is a divisor of 2 etc. Can anyone explain me better how to apply the CRT to this problem? Thank you.

abstract-algebra discrete-mathematics ring-theory chinese-remainder-theorem

share|cite|improve this question

asked Mar 26 at 18:01

JackJack

1047

$endgroup$

share|cite|improve this question

asked Mar 26 at 18:01

JackJack

1047

share|cite|improve this question

asked Mar 26 at 18:01

JackJack

1047

asked Mar 26 at 18:01

JackJack

1047

asked Mar 26 at 18:01

JackJack

1047

2 Answers
2

active

oldest

votes

2

$begingroup$

For any $nge2$, $1+n$ has multiplicative order $n$ modulo $n^2$.
Just observe that
$$(1+n)^kequiv 1+knpmodn^2.$$

share|cite|improve this answer

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I need to use the CRT...
  $endgroup$
  – Jack
  Mar 26 at 18:15
  

  
  
  
  

add a comment | 

0

$begingroup$

We have $$900=2^2times 3^2times 5^2$$

If $gcd(n,900)=1$ then the order of $npmod 900$ is the lcm of its orders $pmod 2^2,3^2,5^2$.

We start $nequiv 2 pmod 25$. Direct computation shows that this has order $20$, so $4$ has order $10pmod 25$.

Now, $4$ has order $3mod 9$, and let's just take $nequiv 1 pmod 4$.

Then we just need to solve $$nequiv 1 pmod 4 quad & quad nequiv 4pmod 225$$

Easy to see that $boxed nequiv 229 pmod 900$ works.

Another approach is simple trial and error. That method quickly gets us to $n=11$ as a smaller solution.

share|cite|improve this answer

answered Mar 26 at 18:16

lulululu

43.7k25081

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's exactly what I haven't understood. How can you find 20? What is the logical consequence to say that 4 has order 10? then you say 4 has order 3mod9... That's exactly the same reasoning of the answer found that I haven't understood.
  $endgroup$
  – Jack
  Mar 26 at 18:23
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The numbers involved are very small. It's easy to simply compute.
  $endgroup$
  – lulu
  Mar 26 at 18:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For instance, with $4pmod 9$, we easily see that $4^2equiv 7$ and $4^3equiv 28equiv 1$.
  $endgroup$
  – lulu
  Mar 26 at 18:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  To be clear: I started with $2$ randomly. It's the smallest candidate, so why not? You could have started with $3pmod 25$ instead. I suggest you do that! It will lead you to a new element of order $30pmod 900$ and it's good practice.
  $endgroup$
  – lulu
  Mar 26 at 18:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, basically, we need to find a common element? You found 4 in $Z_25$ and $Bbb Z_9$... Why do I need to set the two congruences? Why didn't you apply the same reasoning to $Z_4$? What is the correlation between this reasoning with order 30 of a certain element I need to find? You have found "random" elements that have a certain order in each $Z_n$... Sadly, it's not really clear. It isn't a problem of computation but I want to understand clearly the logical order of the steps of your reasoning.
  $endgroup$
  – Jack
  Mar 26 at 19:26
  

  
  
  
  

 | 
show 5 more comments

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%2f3163533%2fhow-to-find-an-element-of-order-30-in-the-multiplicative-group-of-bbb-z-900%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

For any $nge2$, $1+n$ has multiplicative order $n$ modulo $n^2$.
Just observe that
$$(1+n)^kequiv 1+knpmodn^2.$$

share|cite|improve this answer

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I need to use the CRT...
  $endgroup$
  – Jack
  Mar 26 at 18:15
  

  
  
  
  

add a comment | 

2

$begingroup$

For any $nge2$, $1+n$ has multiplicative order $n$ modulo $n^2$.
Just observe that
$$(1+n)^kequiv 1+knpmodn^2.$$

share|cite|improve this answer

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I need to use the CRT...
  $endgroup$
  – Jack
  Mar 26 at 18:15
  

  
  
  
  

add a comment | 

$begingroup$

For any $nge2$, $1+n$ has multiplicative order $n$ modulo $n^2$.
Just observe that
$$(1+n)^kequiv 1+knpmodn^2.$$

share|cite|improve this answer

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

$endgroup$

share|cite|improve this answer

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

answered Mar 26 at 18:12

Lord Shark the UnknownLord Shark the Unknown

109k1163136

0

$begingroup$

We have $$900=2^2times 3^2times 5^2$$

If $gcd(n,900)=1$ then the order of $npmod 900$ is the lcm of its orders $pmod 2^2,3^2,5^2$.

We start $nequiv 2 pmod 25$. Direct computation shows that this has order $20$, so $4$ has order $10pmod 25$.

Now, $4$ has order $3mod 9$, and let's just take $nequiv 1 pmod 4$.

Then we just need to solve $$nequiv 1 pmod 4 quad & quad nequiv 4pmod 225$$

Easy to see that $boxed nequiv 229 pmod 900$ works.

Another approach is simple trial and error. That method quickly gets us to $n=11$ as a smaller solution.

share|cite|improve this answer

answered Mar 26 at 18:16

lulululu

43.7k25081

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's exactly what I haven't understood. How can you find 20? What is the logical consequence to say that 4 has order 10? then you say 4 has order 3mod9... That's exactly the same reasoning of the answer found that I haven't understood.
  $endgroup$
  – Jack
  Mar 26 at 18:23
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The numbers involved are very small. It's easy to simply compute.
  $endgroup$
  – lulu
  Mar 26 at 18:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For instance, with $4pmod 9$, we easily see that $4^2equiv 7$ and $4^3equiv 28equiv 1$.
  $endgroup$
  – lulu
  Mar 26 at 18:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  To be clear: I started with $2$ randomly. It's the smallest candidate, so why not? You could have started with $3pmod 25$ instead. I suggest you do that! It will lead you to a new element of order $30pmod 900$ and it's good practice.
  $endgroup$
  – lulu
  Mar 26 at 18:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, basically, we need to find a common element? You found 4 in $Z_25$ and $Bbb Z_9$... Why do I need to set the two congruences? Why didn't you apply the same reasoning to $Z_4$? What is the correlation between this reasoning with order 30 of a certain element I need to find? You have found "random" elements that have a certain order in each $Z_n$... Sadly, it's not really clear. It isn't a problem of computation but I want to understand clearly the logical order of the steps of your reasoning.
  $endgroup$
  – Jack
  Mar 26 at 19:26
  

  
  
  
  

 | 
show 5 more comments

0

$begingroup$

We have $$900=2^2times 3^2times 5^2$$

If $gcd(n,900)=1$ then the order of $npmod 900$ is the lcm of its orders $pmod 2^2,3^2,5^2$.

We start $nequiv 2 pmod 25$. Direct computation shows that this has order $20$, so $4$ has order $10pmod 25$.

Now, $4$ has order $3mod 9$, and let's just take $nequiv 1 pmod 4$.

Then we just need to solve $$nequiv 1 pmod 4 quad & quad nequiv 4pmod 225$$

Easy to see that $boxed nequiv 229 pmod 900$ works.

Another approach is simple trial and error. That method quickly gets us to $n=11$ as a smaller solution.

share|cite|improve this answer

answered Mar 26 at 18:16

lulululu

43.7k25081

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's exactly what I haven't understood. How can you find 20? What is the logical consequence to say that 4 has order 10? then you say 4 has order 3mod9... That's exactly the same reasoning of the answer found that I haven't understood.
  $endgroup$
  – Jack
  Mar 26 at 18:23
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The numbers involved are very small. It's easy to simply compute.
  $endgroup$
  – lulu
  Mar 26 at 18:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For instance, with $4pmod 9$, we easily see that $4^2equiv 7$ and $4^3equiv 28equiv 1$.
  $endgroup$
  – lulu
  Mar 26 at 18:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  To be clear: I started with $2$ randomly. It's the smallest candidate, so why not? You could have started with $3pmod 25$ instead. I suggest you do that! It will lead you to a new element of order $30pmod 900$ and it's good practice.
  $endgroup$
  – lulu
  Mar 26 at 18:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, basically, we need to find a common element? You found 4 in $Z_25$ and $Bbb Z_9$... Why do I need to set the two congruences? Why didn't you apply the same reasoning to $Z_4$? What is the correlation between this reasoning with order 30 of a certain element I need to find? You have found "random" elements that have a certain order in each $Z_n$... Sadly, it's not really clear. It isn't a problem of computation but I want to understand clearly the logical order of the steps of your reasoning.
  $endgroup$
  – Jack
  Mar 26 at 19:26
  

  
  
  
  

 | 
show 5 more comments

$begingroup$

We have $$900=2^2times 3^2times 5^2$$

If $gcd(n,900)=1$ then the order of $npmod 900$ is the lcm of its orders $pmod 2^2,3^2,5^2$.

We start $nequiv 2 pmod 25$. Direct computation shows that this has order $20$, so $4$ has order $10pmod 25$.

Now, $4$ has order $3mod 9$, and let's just take $nequiv 1 pmod 4$.

Then we just need to solve $$nequiv 1 pmod 4 quad & quad nequiv 4pmod 225$$

Easy to see that $boxed nequiv 229 pmod 900$ works.

Another approach is simple trial and error. That method quickly gets us to $n=11$ as a smaller solution.

share|cite|improve this answer

answered Mar 26 at 18:16

lulululu

43.7k25081

$endgroup$

share|cite|improve this answer

answered Mar 26 at 18:16

lulululu

43.7k25081

answered Mar 26 at 18:16

lulululu

43.7k25081

answered Mar 26 at 18:16

lulululu

43.7k25081