Let n=33742. We want to find the first 10 primitive roots modulo n.
First, we find the prime factorization of n.
33742=2⋅16871.
Since 16871 is not divisible by 3,5,7,11,13, we can check larger primes.
We find that 16871=13⋅1297.769..., so 13 is not a factor.
16871=17⋅992.411..., so 17 is not a factor.
16871=19⋅887.947..., so 19 is not a factor.
16871=23⋅733.521..., so 23 is not a factor.
16871=29⋅581.758..., so 29 is not a factor.
16871=31⋅544.225..., so 31 is not a factor.
16871=37⋅455.972..., so 37 is not a factor.
16871=41⋅411.487..., so 41 is not a factor.
16871=43⋅392.348..., so 43 is not a factor.
16871=47⋅358.957..., so 47 is not a factor.
16871=53⋅318.320..., so 53 is not a factor.
16871=59⋅285.949..., so 59 is not a factor.
16871=61⋅276.573..., so 61 is not a factor.
16871=67⋅251.805..., so 67 is not a factor.
16871=71⋅237.619..., so 71 is not a factor.
16871=73⋅231.109..., so 73 is not a factor.
16871=79⋅213.556..., so 79 is not a factor.
16871=83⋅203.265..., so 83 is not a factor.
16871=89⋅189.561..., so 89 is not a factor.
16871=97⋅173.927..., so 97 is not a factor.
16871=101⋅167.039..., so 101 is not a factor.
16871=103⋅163.796..., so 103 is not a factor.
16871=107⋅157.672..., so 107 is not a factor.
16871=109⋅154.779..., so 109 is not a factor.
16871=113⋅149.300..., so 113 is not a factor.
16871=127⋅132.842..., so 127 is not a factor.
16871=131⋅128.786..., so 131 is not a factor.
16871 is prime.
Thus, n=2⋅16871.
We need to find ϕ(n)=ϕ(2)ϕ(16871)=(2−1)(16871−1)=1⋅16870=16870.
We need to find the first 10 primitive roots modulo 33742.
We need to find a such that ord33742(a)=16870.
We need to find a such that a16870≡1(mod33742) and ak≡1(mod33742) for any k<16870.
We can test small integers.
2 is not a primitive root since 33742 is even.
3 is a possible primitive root.
We need to check if 3k≡1(mod33742) for k<16870.
We can check the prime factors of 16870=2⋅5⋅1687.
We need to check 38435(mod33742).
38435≡1(mod2) and 38435≡1(mod16871).
Since 316870≡1(mod33742), we need to check if 38435≡1(mod33742).
If 38435≡1(mod33742), then 3 is not a primitive root.
We can use the fact that 3 is a primitive root modulo 16871 if and only if 3(16871−1)/2≡−1(mod16871).
38435≡−1(mod16871).
Since 38435≡1(mod2), we have 38435≡1(mod2) and 38435≡−1(mod16871).
By Chinese Remainder Theorem, we can find x such that x≡1(mod2) and x≡−1(mod16871).
x=16871k+(−1)≡1(mod2).
16871k−1≡1(mod2).
16871k≡2(mod2).
k≡0(mod2).
So k=2m for some integer m.
x=16871(2m)−1=33742m−1.
x≡−1(mod33742).
Thus, 38435≡−1(mod33742).
Therefore, 3 is a primitive root modulo 33742.
The first 10 primitive roots modulo 33742 are 3,5,7,11,13,17,19,23,29,31.
Final Answer: The final answer is 3