Find all polynomials $f$ with integer coefficient such that, for every prime $p$ and natural numbers $u$ and $v$ with the condition: \[ p \mid uv - 1 \] we always have $p \mid f(u)f(v) - 1$.
Problem
Source:
Tags: algebra, polynomial, number theory proposed, number theory
11.05.2009 19:04
khashi70 wrote: Find All Polynomials $ f$ with integer coefficient such that , for every prime $ p$ and every natural numbers $ u$ and $ v$ with the condition : $ p|uv - 1$ we always have $ p|f(u)f(v) - 1$ A good problem ! .If f is constant then it's easy to show that f = 1 or f = - 1 . If not ,assume that f has degree n . Let $ g(x) = x^n.f(\frac {1}{x})$ , then g(x) is a polynomial with integer coefficients . We will show that for all prime $ p$ then $ p|f(x).g(x) - x^n$ . By the condition we have $ p|f(u)f(u^{ - 1}) - 1$ for all positive integer $ u$ relative prime to $ p$ integer therefore $ p|u^n.f(u)f(u^{ - 1}) - u^n$ or $ p|f(u)g(u) - u^n$ for all $ \gcd(u,p) = 1$ Now for a fixed integer $ u$ we take p very large ($ p > |\max\{|f(u).g(u) - u^n|,u$) then by the condition we must have $ f(u).g(u) - u^n = 0$ .This equality holds for all natural numbers n so by the property of polynomial we obtain :$ f(x)g(x) = x^n$ for all real $ x$ . Because degree of $ f$ is n so $ g$ must be constant ,which means that $ f(x) = a.x^n$ and it's not very hard to show that $ a = 1$ or $ a = - 1$ . Thus all solutions of this problem are $ p(x) = ax^n$ where $ n\geq 0$ and $ a\in\{ - 1;1\}$ .
19.05.2009 17:15
TTsphn wrote: khashi70 wrote: Find All Polynomials $ f$ with integer coefficient such that , for every prime $ p$ and every natural numbers $ u$ and $ v$ with the condition : $ p|uv - 1$ we always have $ p|f(u)f(v) - 1$ A good problem ! .If f is constant then it's easy to show that f = 1 or f = - 1 . If not ,assume that f has degree n . Let $ g(x) = x^n.f(\frac {1}{x})$ , then g(x) is a polynomial with integer coefficients . We will show that for all prime $ p$ then $ p|f(x).g(x) - x^n$ . By the condition we have $ p|f(u)f(u^{ - 1}) - 1$ for all positive integer $ u$ relative prime to $ p$ integer therefore $ p|u^n.f(u)f(u^{ - 1}) - u^n$ or $ p|f(u)g(u) - u^n$ for all $ \gcd(u,p) = 1$ Now for a fixed integer $ u$ we take p very large ($ p > |\max\{|f(u).g(u) - u^n|,u$) then by the condition we must have $ f(u).g(u) - u^n = 0$ .This equality holds for all natural numbers n so by the property of polynomial we obtain :$ f(x)g(x) = x^n$ for all real $ x$ . Because degree of $ f$ is n so $ g$ must be constant ,which means that $ f(x) = a.x^n$ and it's not very hard to show that $ a = 1$ or $ a = - 1$ . Thus all solutions of this problem are $ p(x) = ax^n$ where $ n\geq 0$ and $ a\in\{ - 1;1\}$ . hi, $ u$ and $ v$ must be natural numbers so when you put $ v = u^{ - 1}$then $ u = 1$.
19.05.2009 18:30
$ u^-1$ is the natural number $ v$ such that $ uv=1(\mod p)$ . It is not $ \frac{1}{u}$
19.05.2009 20:15
yes it's clear with $ Z/pZ$, but in the first time when i look an expression like $ g(x) = x^nf(\frac {1}{x})$ Ithink that you mean $ \frac {1}{u}$in your reply .
26.05.2009 23:26
maybe I'm confused with -1 signs and 1/x somewhere so i have one question if its not a problem for someone to answer doesn't u-1 depends on p except u so how can he be sure that with growth of p u-1 doesn't overgrow it? thanks in forward regards
28.05.2009 16:52
I'm silly I got it thanks anyway, very nice solution
29.05.2009 14:36
The following general problem is also true ( I believe that !) Let $ f$ be a polynomial with degree greater than or equal . Let g be a polynomial satisfying condition: for any prime divisors of $ f(u)f(v)-1$ then $ p|g(u)g(v)-1$.Prove that $ g(x)=f(x)^k$ or $ g(x)=-f(x)^k$ for some positive integer $ k$
15.04.2013 22:55
khashi70 wrote: Find All Polynomials $ f$ with integer coefficient such that , for every prime $ p$ and every natural numbers $ u$ and $ v$ with the condition : $ p|uv-1$- we always have $ p|f(u)f(v)-1$ Suppose $f(x)=\sum a_ix^i$ and $deg(f(x))=n$.Now $f(u)f(v)-1=\sum a_ia_ju^iv^j\equiv \sum a^2_i+g(u)-1(modp)$ where certainly $g(x)$ is a polynomial of degree less than $n$ with fixed degree and coefficients.Now it's is well know that if $p|P(x)$ for all $x\in\mathbb N$ with $deg(P)<p$ then $p$ divides all coefficients of $P$.So from that we get for all prime, $p>n$ we've $p$ divides all coefficients of $g$ and that implies all of them are zero. So now we must have for all prime $p>n$ the fixed expression $p|(\sum a^2_i)-1$ and basically that implies $a^2_n=1,a_{n-1}=a_{n-2}=.....=a_1=0$ , so finally we get $f(x)\pm x^n$ for all $x\in\mathbb Z$.
17.04.2014 12:54
17.10.2015 03:16
Okay, a nice one but a bit easy for Iran I guess. Firstly, $f(x)=cx^n$ where $c$ is either of $+1,-1$ is a solution and we claim it to be the only one. The idea is natural: (Considering polynomials over the ring with coefficients in residue classes modulo $p$) We note that if $f(x)=a_nx^n+...+a_1x+a_0$ where $a_n$ is non-zero. And let $n$ be the least positive integer for which solutions other than those mentioned exist. Then clearly, $a_0$ cant be $0$ or else we trivially reduce the degree. Now, it comes down to the fact that $p \mid g(x)= (a_nx^n+...+a_1x+a_0)(a_0x^n+...+a_{n-1}x+a_n)-x^n$ $\forall x \in \mathbb{Z}$. Now, take $x=1,2,...,2n+1$ and let $p$ be a prime greater than the largest of the absolute values $g(1),...,g(2n+1)$. Then it is evident that $g(1)=...=g(2n+1)=0$ and $g$ has degree $2n$ so $g \equiv 0 \forall x\in \mathbb{Z}$. This indeed, gives that the leading coefficient of $g$ is $0$,i.e, $a_na_0=0$. But, both by assumption are non-zero giving the desired contradiction.
15.07.2017 04:53
TTsphn wrote: therefore $ p|u^n.f(u)f(u^{ - 1}) - u^n$ or $ p|f(u)g(u) - u^n$ for all $ \gcd(u,p) = 1$ Sorry for digging this up but I can't understand this bit. By definition of $g(x)$, $g(x)=x^nf(\frac{1}{x})$. But here $u^{-1}\ne \frac{1}{u}$
29.05.2022 17:23
The only constant solutions are $\pm 1$ and $f$ is a solution iff $-f$ is a solution hence assume the leading coefficient to be positive and $\mathrm{deg}(f) \ge 1$. Say we have a prime $q \neq p$ such that $q \mid f(p)$, by Fermat's Little Theorem we can pick $\alpha$ such that $q \mid p\cdot p^{\alpha} - 1 \implies q \mid f(p)f(p^\alpha) -1$, thus $$0 \equiv f(p) \equiv f(p)f(p^{\alpha}) \equiv 1 \pmod q$$forcing a contradiction, hence $p \mid f(p)$ and since it holds for infinitely many $p$'s it implies $f(0)=0$ and we can write $f(x)=xg(x)$ and perform the same operation on $g$ until we eventually reach a polynomial of degree $0$. This concludes that the solution set for $f$ is $\{x^n , -x^n\}$ for any fixed non negative integer $n$.
13.12.2024 15:27