There are m/(gcd(m,x)) distinct elements in the set {ax(modm):a in {0,...,m−1}} I have only known these by using a computer to generate the number of distinct elements. But I am not sure how to prove this conjecture. And is there any way that we can connect this problem to Euler's phi function so that we can simply use properties of phi function to prove it? And can we also use some counting principle here to give an exact answer?

tamnicufl 2022-09-27 Answered
There are m gcd ( m , x ) distinct elements in the set { a x ( mod m ) : a { 0 , . . . , m 1 } }
I have only known these by using a computer to generate the number of distinct elements. But I am not sure how to prove this conjecture.
And is there any way that we can connect this problem to Euler's phi function so that we can simply use properties of ϕ function to prove it?
And can we also use some counting principle here to give an exact answer?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

panterafan101wx
Answered 2022-09-28 Author has 6 answers
The number of elements in that set is the additive order of x mod m, which as you have observed is m gcd ( m , x ) . This formula is a consequence of lcm ( x , m ) = x m gcd ( m , x ) .

Indeed, we want to know when the sequence a x mod m starts repeating. So find the first a such that a x 0 mod m. This is the same as asking for the first a such that ax is a multiple of m. In other words, a x = lcm ( x , m ).
Did you like this example?
Subscribe for all access
trapskrumcu
Answered 2022-09-29 Author has 2 answers
HINT     m   |   n x     m   |   n x , n m     m   |   ( n x , n m ) = n ( x , m )     m ( x , m )   |   n
Therefore, m o d   m , we conclude that x has order m ( x , m )
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-14
We are supposed to use the Inclusion-Exclusion principle to solve: "how many bridge hands contain exactly 3 clubs, or exactly 5 diamonds or exactly 3 aces?" I know you do something like: |3 clubs|+|3aces|+|5dimonds| - |3clubs AND 3 aces| - |3clubs AND 5 diamonds| -...... +|all 3 intersected| But I'm really struggling with find the cases where the aces may or may not be a club/diamond.
asked 2022-05-03
I am to create a six character password that consists of 2 lowercase letters and 4 numbers. The letters and numbers can be mixed up in any order and I can also repeat the same number and letter as well. How many possible passwords are there?
What I have pieced together so far:
Well, from the fundamental counting principle, we would definitely need 26 2 × 10 4 but obviously this is not all the possibilities since I can rearrange letters and numbers. Since it is a password the order matters so would I try and do a permuation of some sort like 6 P 2 since there are 6 slots to try to rearrange 2 objects (letters)?
asked 2022-07-19
There are two fundamental principles of counting; Fundamental principle of addition and fundamental principle of multiplication.

I often got confused applying them. I know that if there are two jobs, say m and n, such that they can be performed independently in m and n ways respectively, then either of the two jobs can be performed in m + n ways and when two jobs are performed in succession, they can be performed in m × n ways.

My question is how to identify whether jobs are independent or in succession?

Is there any simple way to identify this? Are there any keywords?
asked 2022-05-07
i have a homework with 10 question but im stuck with 3 i searched about them everywhere read other colleges lectures but i couldnt solved them finally i desired to ask here
Question-2:
Prove that each positive integer can be written in form of 2 k q, where q is odd, and k is a non-negative integer.
Hint: Use induction, and the fact that the product of two odd numbers is odd.
Question-6:
( x + y ) n = k = 0 n C ( n , k ) x n k y k = n 2 + n 2
Prove the above statement by using induction on n.
Question-7:
Let n 1 , n 2 , . . . , n t be positive integers. Show that if n 1 + n 2 + . . . + n t t + 1 objects are placed into t boxes, then for some i, i = 1 , 2 , 3 , . . . , t , the ith box contains at least n i objects.
asked 2022-06-20
I believe this question involves the rule of sum and the fundamental counting principle. I think my logic here is wrong, but I hope you could correct it.
(26 P 2 + 26 P 3)(10 P 4) = 8.19*10^7
asked 2022-07-08
How many natural odd numbers are between 100 and 999 that have all different digits?

There are two conditions in this question: (1)the number must be odd and (2)must have all different digits. I thought that condition 1 is more important. So, because tehere is five odd numbers, { 1 , 3 , 5 , 7 , 9 }, the units position has 5 choices. The tens position has 9 choices, since it must be different from the units. The hundreds position has 7 choices, because can't be 0 and must be different from the previous positions.
One gets 7 9 5 = 315. But using Excel I found that there are 320 odd numbers with all different digits between 100 and 999. Where I'm wrong? Thanks
asked 2022-11-23
Determine the number of different ways that the letters of "success" can be arranged

New questions

i'm seeking out thoughts for a 15-hour mathematical enrichment course in a chinese language high faculty. What (pretty) simple concern would you advocate as a subject for any such course?
historical past/issues:
My students are generally pretty good at math, but many of them have no longer been uncovered to rigorous or summary mathematical reasoning. an amazing topic would be one that could not be impossibly hard for students who have by no means written or study proofs in English.
i have taught this magnificence three times earlier than. (a part of the purpose that i'm posting that is that i have used up all my thoughts!) the primary semester I taught an introductory range theory elegance (which meandered its way toward a proof of quadratic reciprocity, though I think this become in the end too advanced/abstract for some of the students). the second one semester I taught fundamental graph idea and packages (with a focal point on planarity and coloring). The 1/3 semester I taught a class at the Rubik's dice.
the students' math backgrounds are pretty numerous: a number of them take part in contest math competitions, and so are familiar with IMO-fashion techniques, however many aren't. a number of them may additionally realize some calculus, however I cannot assume it. all of them are superb at what in the united states is on occasion termed "pre-calculus": trigonometry, conic sections, systems of linear equations (though, shockingly, no matrices), and the like. They realize what a binomial coefficient is.
So, any ideas? preferably, i'd like to find some thing a bit "sexy" (like the Rubik's cube) -- tries to encourage wide variety theory through cryptography seemed to fall on deaf ears, however being capable of "see" institution idea on the cube became pretty popular.
(Responses specifically welcome from folks who grew up in the percent -- any mathematical subjects you desire were protected within the excessive college curriculum?)