Questions tagged [carmichael-function]

For questions on Carmichael functions.

Filter by
Sorted by
Tagged with
1
vote
0answers
19 views

Carmichael number equal to order of an element

Is there always a number like d (mod n) such that ord d (mod n) is equal to the carmichael number of(n) For example Carmichael number of 12 is 2 And order 5 mod(12) is 2 I tried to handle it using ...
1
vote
2answers
68 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
24 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
40 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
64 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, ...
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
1answer
677 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
67 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)...
1
vote
1answer
61 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
0answers
57 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$?
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 ...
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
50 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
137 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 ) ? ...
2
votes
2answers
175 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 ...
8
votes
5answers
608 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....
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 ...
1
vote
0answers
165 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 ...
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
669 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
232 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 ...