Questions tagged [carmichael-function]

For questions on Carmichael functions.

1
vote
2answers
67 views

Proving that Carmichael function divides Euler's totient function with division

I was looking at a proof for $\lambda(n) | \phi(n)$ using division. Assume $\lambda(n) \not| \phi(n).$ Then $\phi(n) = \lambda(n) * q + r$ and $ 1 \leq r \leq \lambda(n) -1.$ $1 = a^{\phi(n)} = a^...
0
votes
1answer
29 views

Does $C(n)$ grow exponential versus $n$?

Let $λ(m)=n$ be the Carmichael Function of $m$. For each (even) number $n$, there is a largest number $m$ such that $λ(m)=n$. Let $C(n)$ denote the largest integer $m$ such that $λ(m)=n$. For instance,...
0
votes
1answer
23 views

Modular exponentiation with the Carmichael function

This is something I have been thinking of using in a math competition against other players so it would be very helpful to me if it was explained. How would someone reduce a problem such as $\frac{7^{...
0
votes
2answers
39 views

Clarification about Carmichael's Lambda Function

By definition Carmichael function $\lambda(n)$ is the the smallest positive integer $m$ such that $$ x^m\equiv 1\pmod{n} $$ for all $1\leq x\leq n$ such that $\gcd(x,n)=1$. Moreover it is simple to ...
1
vote
0answers
61 views

Are these limits correct? $\lim_{n\to \infty}\text{sup} \frac{\lambda (n)}{n}=1$ and $\lim_{n\to \infty}\text{inf} \frac{\lambda (n)}{n}=0$ exist?

I learned that from here for Euler totient function $\phi (n)$ , we have $$\lim_{n\to \infty}\text{sup} \frac{\phi (n)}{n}=1$$ $$\lim_{n\to \infty}\text{inf} \frac{\phi (n)}{n}=0$$ However, ...
1
vote
1answer
662 views

How is Carmichael's function subgroup of Euler's Totient function?

I've seen this question. I'm trying to find the connection between Euler's totient function and Carmichael's function. Carmichael's function outputs smallest $k$ such that: $a^k ≡ 1 \pmod n$ Euler'...
0
votes
0answers
65 views

Is the order of integers mod p under multiplication output of Carmichael's function?

I've been trying to understand the group theory proof of Fermat's little theorem. Let's say there exists group $G = (ℤ/pℤ)^x$, and it has multiplicative subgroup $H$ (a monoid group, as i understand)...
2
votes
0answers
56 views

There are infinitely many $n$ such that $\lambda(n) = k$?

There are infinitely many $n$ such that $\lambda(n) = k$ (Carmichael function)? For example: $k = 4$. How efficiently we can generate all $n$ for which $\lambda(n) = 4$?
1
vote
1answer
60 views

Is there any way to find a number N if it's Carmichael function is given.

I know to find the Carmichael function [ C() ] of a given no. But I want to know if there is any method or shortcut to find a number N if it's C() is given.
2
votes
1answer
89 views

Shortest repeating digits in fractions.

If you have an integer of $n$ decimal digits that is odd and non-divisble by $5$ then what is the shortest repeating decimal it can have in its reciprocal? Can it be as small as $n^c$ digits for some ...
3
votes
1answer
6k views

What is the state of Carmichael's totient function conjecture?

I have been searching for information about that conjecture and it seems for me that noone has made any significant improvement on it in the last 30 years. Is that true? Does it remain unproven to be ...
1
vote
0answers
25 views

Suppose that $n$ is a composite, squarefree integer such that for every prime divisor $p$ of $n$… [duplicate]

Suppose that $n$ is a composite, squarefree integer such that for every prime divisor $p$ of $n$, we have $(p - 1) | (n - 1)$. Prove that $n$ is a Carmichael number. Having a lot of trouble with this ...
0
votes
0answers
63 views

Why does PARI output different results here?

...
0
votes
0answers
49 views

For which numbers, every possible order can be achieved?

Let $n\ge 2$ be a natural number. Then, every possible order of an number modulo $n$ is a divisor of $\lambda(n)$. $\lambda(n)$ is the Carmichael-function, it is the largest possible order modulo $n$....
1
vote
2answers
132 views

What is the largest number $n$ with $\lambda(n)=k$ for a given $k$?

Let $k\ge 2$ be a natural number. What is the largest number $n$ with $\lambda(n)=k$, where $\lambda(n)$ is the Carmichael-function. (See : https://en.wikipedia.org/wiki/Carmichael_function ) ? ...
3
votes
1answer
47 views

the least $m$ such that $a^m\equiv 1 \mod n $ for fixed $a,n$.

Is there any known method for calculating $\lambda_a(n)$ which returns the smallest integer $m$ such that $a^m\equiv 1 \pmod n$ where $\gcd(a,n)=1$ ? I searched but I found nothing, is there at ...
8
votes
5answers
600 views

The maximal size of between $\varphi(n)$ divided by $\lambda(n)$.

I want to find $$f(n) = \max\left\{\frac{\varphi(k)}{\lambda(k)} : 1 \leq k \leq n\right\}$$ In other words, I want to find the maximal value of $\frac{\varphi(k)}{\lambda(k)}$ when $k$ is restricted....
1
vote
0answers
162 views

Carmichael function and primitive roots of unity

I have been reading about the Carmichael function recently and I would like to ask about some elementary implication of its properties as I haven't found it stated explicitly. If I understand it ...
2
votes
2answers
173 views

How many Fermat tests are needed to verify a Carmichael number

If $n$ is a Carmichael number, then for all values $a$ such that $0<a<n$ (and $a \perp n$): $a^{n-1} \equiv 1 \mod n$ However, is it not necessary to check check all $a$ values because for a ...
3
votes
1answer
63 views

Implication related to carmichael function.

If $g \in \Bbb Z_{n^2}^{*}$ and $x_1,x_2 \in \Bbb Z_n$ then help me in proving the following implication. $g^{n \lambda(n)}\equiv 1 \mod{n^2} \implies g^{(x_1-x_2)\lambda(n)} \equiv 1 \mod{n^2}$ ...
2
votes
1answer
1k views

Proof for Carmichael theorem

if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_r^{a_r}$ and $\lambda(n) = lcm[(p_1-1)(p_1^{a_1-1}),(p_2-1)(p_2^{a_2-1}),(p_3-1)(p_3^{a_3-1}),\dots,(p_r-1)(p_r^{a_r-1})]$ then $k^{\lambda{n}} \equiv 1(...
1
vote
1answer
659 views

Relationship between the Carmichael function and Euler's totient function

Let $\lambda$ denote the Carmichael function and $\varphi$ Euler's totient function. Furthermore, let $p$ denote any prime number and $k\in\mathbb{N}$. The wikipedia article about $\lambda$ states: $$\...
3
votes
1answer
230 views

Carmichael function available in PARI / GP?

Is the Carmichael function $\lambda(n)$ available in PARI / GP or do I have to program it ? I know the command znorder, but this does not seem to be enough to calculate the carmichael function. I ...