2
$\begingroup$

I am trying to understand the standard way to estimate the number of integers relatively prime to $6$ where we don't know which congruence class $x$ belongs to.

For a given $x$, if we know the congruence class, it is straight forward to determine the number of integers between $1$ and $x$ that are relatively prime to $6$.

If $x \equiv 0 \pmod 3$, the answer is $\frac{x}{3}$: i.e., between $1$ and $9$, there are $3$ that are relatively prime: $\{ 1, 5, 7\}$

If $x \equiv 1 \pmod 6$, the answer is $\frac{x+2}{3}$: ie., between $1$ and $7$, there are $3$.

If $x \equiv 2 \pmod 3$, the answer is $\frac{x+1}{3}$

if $x \equiv 4 \pmod 6$, the answer is $\frac{x-1}{3}$

What be the standard answer for $x$ where we don't know the congruence class?

Would we say between $\frac{x-1}{3}$ and $\frac{x+2}{3}$?

What would be the right way for any $x$ to estimate the number of integers relatively prime to $6$?

$\endgroup$
  • $\begingroup$ An example estimate would be $\frac x3$ for large $x$, to highest order, with absolute error at most $\frac 23$. If you want a formula for the exact number there are ways of doing that. $\endgroup$ – Mark Bennet Nov 10 '15 at 21:27
  • $\begingroup$ @LarryFreeman $x/3$ ...............no? $\endgroup$ – martin Nov 10 '15 at 21:27
  • $\begingroup$ Hi @Martin, that would be incorrect betwen $1$ and $2$. The correct answer is $1$ but $\frac{2}{3}$ would not be correct. $\endgroup$ – Larry Freeman Nov 10 '15 at 21:31
  • 1
    $\begingroup$ @LarryFreeman well, seq[nn_] := With[{aa = (ConstantArray[1, #] & /@ Table[3 + (-1)^n, {n, 0, Ceiling[nn/3]}])}, Take[Flatten[aa*Range@Length@aa], nn]] and then seq[50]gives sequence up to $50,$ as to defining it using correct mathematical notation, I will give it some thought... $\endgroup$ – martin Nov 10 '15 at 21:42
  • 1
    $\begingroup$ One way of estimating the error is to use periodic functions like sixth roots of unity to the power $n$ - this will give an exact and algebraic expression. Other ways involve floor functions etc, which are simpler in some ways, but not in others. $\endgroup$ – Mark Bennet Nov 10 '15 at 21:43
2
$\begingroup$

The number of integers relatively prime to $6$ for each $x$ is given by the expression

$$\left\lfloor \frac{x-1}{6}\right\rfloor +\left\lfloor \frac{x+1}{6}\right\rfloor +1$$

which is clearly $\sim x/3.$

Check:

rp6[x_] := Floor[(x - 1)/6] + Floor[(x + 1)/6] + 1

{Length@Select[Range@#, GCD[#, 6] == 1 &] & /@ Range@40, 
rp6@# & /@ Range@40} // ListLinePlot

Generalisation:

The number of integers relatively prime to $n$ for each $x$ is $\sim x \cdot \phi(n)/n,$ where $\phi$ is the Euler totient function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.