All Questions
Tagged with prime-factorization modular-arithmetic
93
questions
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 ...
1
vote
2
answers
221
views
Find the least odd prime factor of $155^8+1$
Find the least odd prime factor of $155^8+1$. How do I do this without using Wolfram Alpha or something?
1
vote
0
answers
122
views
Sum of members from multiplicative group of prime order $k$ modulo prime $P$? $c$ in: $\sum_{n=1}^{k} (g^n \bmod P) = c \cdot P$ ($g$ prime order $k$)
Let $P$ be a prime ($>2$) and $g$ a value between $2$ and $P-2$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a ...
2
votes
1
answer
106
views
Integer Factor Congruence
Given an integer $N$, with unknown prime factors $f_1$, $f_2$ ... $f_n$, and given unique integers $k_1$, $k_2$ ... $k_n$, with $\sqrt{N} \geq k_i>2$ for all $i$ such that
$$f_1 \equiv 1\pmod {k_1}$...
9
votes
3
answers
371
views
Can $7$ be the smallest prime factor of a repunit?
Repunits are numbers whose digits are all $1$. In general, finding the full prime factorization of a repunit is nontrivial.
Sequence A067063 in the OEIS gives the smallest prime factor of repunits. ...
3
votes
1
answer
126
views
The proof of $(n+1)!(n+2)!$ divides $(2n+2)!$ for any positive integer $n$
Does $(n+1)!(n+2)!$ divide $(2n+2)!$ for any positive integer $n$?
I tried to prove this when I was trying to prove the fact that ${P_n}^4$ divides $P_{2n}$ where $n$ is a positive integer, where $P_{...
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 ...
1
vote
1
answer
80
views
Given 2 functions $f(x)$ and $g(x)$ find a value where $g(x)$ divides $f(x)$ meaning $f(x) = 0 \mod g(x)$
Problem:
Given 2 functions $f(x) = 2^{p-1} + x*p$ and $g(x) = 2 * x * p + 1$ find the values where $f(x) = 0 \mod{g(x)}$, where $p$ is a prime number and $x$ is a non negative integer in the range $1,...
0
votes
1
answer
154
views
How to find the prime factors when knowing some congruence?
In order to factorize the integer $N = 67591$, choose a factor base $\{2,3,5\}$ and four congruences: $24256^2 \equiv 2^9 \cdot 3^4(mod\ N)$; $59791^2 \equiv 2^2 \cdot 3^4\cdot 5^2(mod\ N)$; $23541^2 \...
0
votes
2
answers
114
views
Proving the divisibility of $4[(n-1)!+1]+n$ by $n(n+2)$ in the condition of $n,n+2 \in P$ where $P$ is the set of prime numbers [duplicate]
Let $n$ and ($n+2$) be two prime numbers. If any real value of $n$ satisfies that condition, then prove that $$\frac{4{[(n-1)!+1]}+n}{n(n+2)} = k$$ where $k$ is a positive integer.
SOURCE: BANGLADESH ...
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
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 ...
1
vote
1
answer
89
views
Find X in the Equation
I'm not a mathematician and I have forgotten about some basics in mathematics.
I have this equation:
$$x^y \pmod z = w$$
Given $y, z,$ and $w,$ how will I find $x$? How will I get the equation for $...
0
votes
0
answers
79
views
Finding the smallest prime factor of $\sum_{a=1}^N a^{k}$
This question is linked to my previous question, but I wanted a clearer explanation.
Suppose we have a huge number of that type with a huge $k$.
$$\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k},$$
...
0
votes
1
answer
165
views
Find the smallest positive prime divisor of ...
Problem:
That's a problem I have found on the web. I didn't understand the solution:
Why??
Given solution:
How all this sequence has been transformed into $$33-{\lfloor {33\over p}\...