Skip to main content

Questions tagged [carmichael-function]

For questions on Carmichael functions.

Filter by
Sorted by
Tagged with
0 votes
0 answers
22 views

Why order of $a$ co-prime to $n$ traverses all factors of carmichael function of $n$? -Is it true?

I'm recently a bit indulged with basic number theory and investigating in the Carmichael $\lambda(n)$ function, which is defined as the smallest positive number that makes $a^x\equiv\ (\mathrm{mod}\ n)...
Colin Lee's user avatar
1 vote
0 answers
142 views

Finding a General Explicit Formula for $\lambda(n)$ for when $n\neq p^k$

I have been trying to answer the following question: Is there a general formula for Carmichael's totient function ($\lambda(n)$) that is analogous to the Euler product formula for Euler's totient ...
Yajat Shamji's user avatar
2 votes
0 answers
95 views

On Carmichael function and aliquot parts of odd perfect numbers

This post is cross-posted on MathOverflow with identifier 439563 and same title. We denote as $N$ an odd perfect number, and $d\mid N$ one of its divisors. We denote the Carmichael function as $\...
user759001's user avatar
0 votes
0 answers
53 views

Alternative definition for carmichael function

As my textbook describes it, the Carmichael function is the minimum integer m such that, for all a coprime with n, $$a^m \equiv 1 \pmod{n}$$ So, as far as I understand it, m is the minimum number that:...
Giorgio Ciotti's user avatar
1 vote
0 answers
46 views

When does a solution of $m+\lambda(m)=n$ exist?

Let $\lambda(m)$ be the Carmichael-function. For which positive integers $n$ does a positive integer $m$ exist with $m+\lambda(m)=n$ ? In other words, for which $n$ is $m+\lambda(m)=n$ solvable ? Of ...
Peter's user avatar
  • 85k
4 votes
0 answers
110 views

A346587: which numbers maximize $\frac{n}{\lambda(n)}$?

This is the sequence of $n$ so that $\frac{n}{\lambda(n)}$ is greatest up until $n$, where $\lambda$ is the Carmichael function. The analogous quantity $\frac{n}{\varphi(n)}$ is maximized when $n$ is ...
Derivative's user avatar
  • 1,788
4 votes
1 answer
490 views

Carmichael function and the largest multiplicative order modulo n [duplicate]

By definition, the Carmichael function maps a positive integer $n$ to the smallest positive integer $t$ such that $a^t\equiv1\pmod n$ for all integers $a$ with $\gcd(a,n)=1$. It is denoted as $\lambda(...
Iming Cheng's user avatar
11 votes
1 answer
437 views

Do $\lambda(n)$ and $\pi(n)$ coincide infinitely often?

Let $\pi(n)$ be the prime-counting function and $\lambda(n)$ the Carmichael-function. Does $$\pi(n)=\lambda(n)$$ hold for infinite many positive integers $n$ ? I have no idea for an approach other ...
Peter's user avatar
  • 85k
7 votes
1 answer
66 views

Does the fraction of positive integers not being a Carmichael value have a limit?

Let $f(n)$ be the number of positive integers $x\le n$ such that $\lambda(k)=x$ has no solution, where $\lambda(k)$ denotes the Carmichael-function. Does $$\lim_{n\rightarrow \infty} \frac{f(n)}{n}$$ ...
Peter's user avatar
  • 85k
0 votes
0 answers
114 views

Why is $\ 100\ $ so special in this context?

Let $\ \lambda(k)\ $ be the Carmichael function and denote $\ N(n)\ $ to be the number of solutions of $\ \lambda(k)=n\ $ Can we prove that $\ N(n)=n\ $ only holds for $\ n=100\ $ (besides the ...
Peter's user avatar
  • 85k
5 votes
1 answer
218 views

Conjecture about the Carmichael function

Let $\ \lambda(n)\ $ denote the Carmichael-function and define $\ n(e)\ $ to be the number of solutions of $\ \lambda(m)=e\ $. For $\ e\ge 3\ $ , we have $\ 4\mid n(e)\ $ I chose "$\ e\ $" ...
Peter's user avatar
  • 85k
1 vote
1 answer
98 views

Can the Carmichael Function be used with Proof By Infinite Descent in the following way?

I was reading up on the Carmichael Function and I had a question about its use. Can it be used to show that if $x > 1$, then $n=1$ for: $$2^m(2^x - 1) = 3^n(3^y - 1)$$ Here's the argument that I ...
Larry Freeman's user avatar
2 votes
1 answer
250 views

When is $\lambda (n)$ = $\phi (n)$?

$\lambda (n)$ is the Carmichael function and $\phi (n)$ is the Euler totient function. I can see that if $n$ is prime then the two functions agree and also if $n$ is a power of a prime they agree. Are ...
thestar's user avatar
  • 169
4 votes
0 answers
34 views

Addition to previously asked question on Generalized Carmichael Numbers

I had previously asked a question on mathstack exchange (Conjecture on The Generalized Carmichael Numbers) concerning with a conjecture I had discovered. I worked on the problem for a long time and ...
BookWick's user avatar
  • 419
3 votes
0 answers
68 views

Conjecture on The Generalized Carmichael Numbers

Define $$C_k = \{n \in \mathbb{Z}: n > \max(k, 0) \text{ }\text{and}\text{ }a^{n - k + 1} \equiv a \pmod{n} \text{ }\text{for all} \text{ } a \in \mathbb{Z}\}$$ Thus it's easy to see that when $k = ...
BookWick's user avatar
  • 419
1 vote
0 answers
64 views

Can we have $n^2\mid m^m-1$ for another $n\ge 3$?

This question is related to this but instead of $\varphi(n)$ it ask about a solution , if we replace it by the Carmichael function $\lambda(n)$ I rule out $n=1$ and $n=2$ since in this case we have $\...
Peter's user avatar
  • 85k
2 votes
1 answer
227 views

Fermat's little theorem, Poulet numbers, Carmichael numbers, and primes

Fermat's primality test for base 2 permits Poulet numbers to pass the test, as follows: $(2^x - 2)/x$. Fermat's primality test in different bases will act as a sieve for eliminating most pseudo ...
Ilan Alon's user avatar
1 vote
0 answers
102 views

repeating decimals and carmichael function

Wikipedia states here: For an arbitrary integer $n$ the length $\lambda (n)$ of the repetend of $1/n$ divides $\phi (n)$, where $\phi$ is the totient function. In the next section, it defines $\...
rocksNwaves's user avatar
3 votes
2 answers
201 views

wondering about multiplicative (not arithmetic) sequences of primes

(Apologies in advance if the terminology is wrong). I've been led by my research into looking at sequences of primes of the form $(p_1,p_2,\ldots,p_m)$ with each $p_i$ of the form $k_i(p_1-1)+1$, ...
Barry Fagin's user avatar
1 vote
2 answers
879 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^...
johnnyB's user avatar
  • 45
0 votes
1 answer
71 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,...
J. Linne's user avatar
  • 3,042
0 votes
1 answer
86 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^{...
Aebii's user avatar
  • 70
0 votes
2 answers
206 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 ...
Alex's user avatar
  • 643
1 vote
0 answers
271 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, I could ...
user avatar
1 vote
1 answer
1k 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'...
ShellRox's user avatar
  • 977
0 votes
0 answers
201 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)...
ShellRox's user avatar
  • 977
2 votes
0 answers
70 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$?
Aurelio's user avatar
  • 489
0 votes
1 answer
135 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.
Yami Kanashi's user avatar
2 votes
1 answer
132 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 ...
Turbo's user avatar
  • 6,251
4 votes
1 answer
7k 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 ...
user3141592's user avatar
  • 1,869
1 vote
0 answers
48 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 ...
Nick Powers's user avatar
1 vote
0 answers
65 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$....
Peter's user avatar
  • 85k
1 vote
2 answers
291 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 ) ? ...
Peter's user avatar
  • 85k
3 votes
1 answer
65 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 ...
Tulip's user avatar
  • 4,896
9 votes
5 answers
702 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....
wythagoras's user avatar
  • 25.2k
1 vote
0 answers
248 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 ...
glamredhel's user avatar
2 votes
2 answers
325 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 ...
Dane Bouchie's user avatar
  • 1,282
3 votes
1 answer
82 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}$ ...
hanugm's user avatar
  • 2,363
1 vote
1 answer
2k 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(...
hanugm's user avatar
  • 2,363
2 votes
1 answer
2k 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: $$\...
0xbadf00d's user avatar
  • 13.8k
3 votes
1 answer
390 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 ...
Peter's user avatar
  • 85k