All Questions
34
questions
0
votes
0
answers
42
views
About the proof of reduction of factoring to order finding
Inside the book I'm following there's a theorem, used to prove the factoring algorithm, which states:
Suppose $N = p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{m}^{\alpha_m}$ is the prime factorization of ...
2
votes
1
answer
68
views
How to solve $x^x \equiv 0 \pmod y$
Given a constant y, I am trying to find the smallest value for x that satisfies the equation $x^x = 0 \mod y$. So far I have been able to determine that $x$ is equal to the product of all the prime ...
- 21
3
votes
1
answer
147
views
Is the number of ways to express a number as sum of two coprime squares same as number of solution of $x^2+1\equiv0\pmod n$
The number of representations of $n$ by sum of 2 squares is known as sum of square function $r_2 (n)$. It is known that if prime factorization of $n$ is given as
$$2^{a_0}p_1^{a_1}p_2^{a_2}\cdots q_1^{...
- 3,589
4
votes
0
answers
243
views
Proper divisors of $P(x)$ congruent to 1 modulo $x$
Let $P(x) $ be a polynomial of degree $n\ge 4$ with integer coefficients and constant term equal to $1$. I am interested in Polynomials $P(x) $ such that for a fixed positive integer $b$, there are ...
- 234
-1
votes
1
answer
161
views
Computing (quickly) the multiplicity of a (prime) divisor
Question
I have a fixed, prime d and an n < 2⁶⁴, and I want not only to compute whether d ...
- 99
1
vote
2
answers
162
views
Finding all no-congruent primitive roots $\pmod{29}$
Finding all no-congruent primitive roots $\pmod{29}$.
I have found that $2$ is a primitve root $\pmod{29}$
Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$
Then I ...
- 113
0
votes
1
answer
44
views
Does there always exist a prime $q\equiv3\mod 4$ that divides $p+a^2$ with $p\equiv1$ mod 4
Let $p$ be a prime such that $p\equiv1\mod4$. Is it true that there will always exist a prime $q$ that satisfies $q\vert(p+a^2)$ and $q\equiv3\mod4$, for some integer $a$?
I have tried proceeding by ...
- 103
1
vote
1
answer
128
views
For $n \ge 4$ find a factorization $n^2 - 3n + 1 = ab$ where $a \lt n$ and $b \lt n$.
Update: We can use Willie Wong's argument to justify the definition of a 'truth cutoff' function,
$\quad \psi: \{3,4,5,6, \dots \} \to \{4,5,6,7, \dots \}$
For convenience we start with a ...
- 11.5k
0
votes
1
answer
196
views
Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Question: Calculate all prime numbers $x$, where $x^{18} - 1$ is divisible by $28728$
Apparently, the answer is all prime numbers except $2, 3, 7,$ and $19.$ I did some prime factorisation and found ...
- 315
1
vote
2
answers
79
views
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $x\in\mathbb{N}$, is $5$ or $1$ mod $5$
We can write the "polynomial" as follows:
$$x^4+x^3+x^2+x+1=\frac{x^5-1}{x-1}.$$
For even $x=2y$, we have that $x^5-1=(2y)^5-1=32y^5-1\equiv1$ mod $5$.
For odd $x=2y+1$, we have that $(2y+1)^5-1\...
- 1,674
1
vote
0
answers
43
views
Non-Linear Diophantine Equation in Two Variables [duplicate]
How many solutions are there in $\mathbb{N}\times \mathbb{N}$ to the equation $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{1995}$ ? I could solve till I got to the point where $1995^2$ is equal to the ...
- 344
7
votes
2
answers
2k
views
What is the multiplicative order of a product of two integers $\mod n$?
Standard texts prove that $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ when $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. What if they are not relatively prime? Here $\textrm{...
- 11.8k
2
votes
1
answer
142
views
The Chinese hypothesis revisited
In the past I tried to get different variations of the so-called Chinese hypothesis, see this Wikipedia (a disproven conjecture).
Today I wanted to combine in an artificious way also Wilson-Lagrange ...
user243301
3
votes
0
answers
114
views
If 13 does not divide m, then prove that $m^4+8$ is not a cube of an integer [closed]
My question is how can we prove that $m^4 + 8$ not a cube of an integer if
$m$ can not be divided by 13.
What I have done so far:
By Fermat’s Little Theorem:
\begin{align}
m^{p-1} &\equiv 1 \...
- 111
2
votes
1
answer
115
views
Prime factors of $5 n^4 - 70 n^3 + 380 n^2 - 945 n + 911 $
Let $n$ be an integer.
Then any prime factor of
$$ 5 n^4 - 70 n^3 + 380 n^2 - 945 n + 911 $$
Must be congruent to 1 mod 10.
Also
Let $n$ be an integer.
Then any prime factor of
$$ 5 n^4 - 10 n^3 +...
- 16.4k