All Questions
Tagged with prime-factorization modular-arithmetic
10
questions
16
votes
6
answers
16k
views
prime divisor of $3n+2$ proof
I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof
I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+...
- 2,935
7
votes
0
answers
174
views
I found a way to calculate Quadratic min mod $N$, but why does it work?
I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:
$$a^2\equiv b(\mod{N})$$
If I am able to find $b$ that is a perfect square, I will be able to factor $N$...
- 1,450
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
8
votes
2
answers
234
views
Is $every$ prime factor of $\frac{n^{163}-1}{n-1}$ either $163$ or $1\;\text{mod}\;163$?
This was inspired by this question. More generally, given prime $p$ and any integer $n>1$, define,
$$F(n) = \frac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+\dots+1$$
Q: Is every prime factor of $F(n)$ either ...
- 54.9k
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
2
answers
251
views
How does one prove that $(2\uparrow\uparrow16)+1$ is composite?
Just to be clear, close observation will show that this is not the Fermat numbers.
I was reading some things (link) when I came across the footnote on page 21, which states the following:
$$F_1=2+1\...
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
1
vote
2
answers
3k
views
Fermat’s Little Theorem can be used to prove a given number is not prime
Present an argument using Fermat’s Little Theorem to show that $341$ is not a prime number.
How do we go about this? Would $a=7$ work?
- 157
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
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}\...
- 349