Mathematics

#6: Post edited by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-24T01:19:44Z (3 months ago)
Removed edit message

Copy Link

Raw

Markdown

(Edit: the math doesn't seem to be rendered as expected. I have posted about this in [Meta](https://math.codidact.com/posts/292113). As a temporary fix, edit the question and change some of the text to refresh the renderer.)
$\require{centernot}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I certainly might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

$\require{centernot}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I certainly might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

#5: Post edited by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-24T01:16:02Z (3 months ago)
Removed amsmath

Copy Link

Raw

Markdown

(Edit: the math doesn't seem to be rendered as expected. I have posted about this in [Meta](https://math.codidact.com/posts/292113). As a temporary fix, edit the question and change some of the text to refresh the renderer.)
~~\( equire{centernot}\require{amsmath}\)~~
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I certainly might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

(Edit: the math doesn't seem to be rendered as expected. I have posted about this in [Meta](https://math.codidact.com/posts/292113). As a temporary fix, edit the question and change some of the text to refresh the renderer.)
$ equire{centernot}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I certainly might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

#4: Post edited by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-23T08:32:24Z (3 months ago)
Edit comment

Copy Link

Raw

Markdown

$\require{centernot}\require{amsmath}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

(Edit: the math doesn't seem to be rendered as expected. I have posted about this in [Meta](https://math.codidact.com/posts/292113). As a temporary fix, edit the question and change some of the text to refresh the renderer.)
$\require{centernot}\require{amsmath}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I certainly might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

#3: Post edited by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-23T08:13:34Z (3 months ago)
Neater formatting

Copy Link

Raw

Markdown

> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $\require{centernot}ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
~~Therefore, the only solution is $f(x)=x$. $\require{amsmath}\blacksquare$~~
</details>
However, I might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need to show that all such functions have been considered? If so, how do we?

$\require{centernot}\require{amsmath}$
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\blacksquare$
</details>
However, I might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need []()to show that all such functions have been considered? If so, how do we?

#2: Post edited by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-23T08:09:27Z (3 months ago)
Rendering

Copy Link

Raw

Markdown

~~$\require{centernot}\require{amsmath}$~~
> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
~~Therefore, the only solution is $f(x)=x$. $\blacksquare$~~
</details>
However, I might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need to show that all such functions have been considered? If so, how do we?

> Find all functions $f:\mathbb N\to\mathbb N$ such that for all primes $p$, \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if $p\mid a-b$.
<details>
<summary>My proposed solution:</summary>
Notice that $p\mid a-b\iff a\equiv b\pmod p$ and by Euler's theorem, $p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p$.
This must hold true when $a=b$, and therefore we get that $f(a)^{f(p)}\equiv f(a)\pmod p$ for all $a$. This holds only for a limited number of functions:
1. $f(x)=x$, and we can easily check that $f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p$ which fulfills the above conditions.
2. $f(x)=cx-c+1$ for some natural number $c>1$, which leads to $f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p$. But this doesn't exclusively hold when $a\equiv b\pmod p$, as $\require{centernot}ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p$. Therefore, this does not fulfill the "only if" condition.
3. $f(x)=x^n$ for some natural number $n>1$, which leads to $f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p$. But similar to the what we previously considered, $a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p$ and this does not fulfill the "only if" condition.
4. $f(x)=\varphi(x)+1$ where $\varphi(x)$ is Euler's totient function, but $a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p$ and therefore this does not satisfy the requirements.
5. $f(x)=1$, which does not satisfy the "only if" condition.
Therefore, the only solution is $f(x)=x$. $\require{amsmath}\blacksquare$
</details>
However, I might've missed another function $f:\mathbb N\to\mathbb N$ that fulfills the conditions. For a rigorous proof, would we need to show that all such functions have been considered? If so, how do we?

#1: Initial revision by $user avatar$ TheCodidacter, or rather ACodidacter‭ · 2024-07-23T07:58:47Z (3 months ago)

Copy Link

Raw

Markdown

Find all functions \(f:\mathbb N\to\mathbb N\) such that for all primes \(p\), \(p\mid f(a)^{f(p)}-f(b)^p\iff p\mid a-b\)

\(\require{centernot}\require{amsmath}\)

> Find all functions \(f:\mathbb N\to\mathbb N\) such that for all primes \(p\), \[p\mid f(a)^{f(p)}-f(b)^p\] if and only if \(p\mid a-b\).


<details>
<summary>My proposed solution:</summary>

Notice that \(p\mid a-b\iff a\equiv b\pmod p\) and by Euler's theorem, \(p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p\).

This must hold true when \(a=b\), and therefore we get that \(f(a)^{f(p)}\equiv f(a)\pmod p\) for all \(a\). This holds only for a limited number of functions:

1. \(f(x)=x\), and we can easily check that \(f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p\) which fulfills the above conditions.

2. \(f(x)=cx-c+1\) for some natural number \(c>1\), which leads to \(f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p\). But this doesn't exclusively hold when \(a\equiv b\pmod p\), as \(ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p\). Therefore, this does not fulfill the "only if" condition.

3. \(f(x)=x^n\) for some natural number \(n>1\), which leads to \(f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p\). But similar to the what we previously considered, \(a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p\) and this does not fulfill the "only if" condition.

4. \(f(x)=\varphi(x)+1\) where \(\varphi(x)\) is Euler's totient function, but \(a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p\) and therefore this does not satisfy the requirements.

5. \(f(x)=1\), which does not satisfy the "only if" condition.

Therefore, the only solution is \(f(x)=x\). \(\blacksquare\)

</details>

However, I might've missed another function \(f:\mathbb N\to\mathbb N\) that fulfills the conditions. For a rigorous proof, would we need to show that all such functions have been considered? If so, how do we?

functions solution-verification modular-arithmetic

Communities

Post History