All Questions
Tagged with prime-factorization modular-arithmetic
93
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
10
votes
1
answer
1k
views
When is $(p-2)!-1$ power of $p$ if $p$ is prime?
If $p$ is prime, for what values of $p$ is $(p-2)!-1$ a power of $p$? I know how to solve that when $p<5$ then $(p-1)!+1$ can be written as power of $p$.
- 315
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. ...
- 221
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
7
votes
1
answer
214
views
Pattern in number theory, proof explanation?
So I was playing around the other day, contemplating an application of the combination of products and sums. I took the sum
$$1+2+3+\dotsc+n=\frac n2(n+1)=S_n$$ and divided it by $n!$. I realized ...
- 71
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
5
votes
2
answers
1k
views
What software can calculate the order of $b \mod p$, where $p$ is a large prime?
I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers.
I have no background whatsoever in number theory, and I need to find software that can calculate the ...
- 191
5
votes
4
answers
136
views
If $x \not \equiv 1 \pmod 3$, when is $x^2 + x +1$ not a prime?
If $x \not\equiv1 \pmod 3$, when is $x^2 + x + 1$ not a prime?
I am especially interested in an example that is not prime or even better, an explanation why the frequency of such primes goes down as $...
- 10.5k
5
votes
1
answer
224
views
An approximation for $1\leq n\leq N$ of the number of solutions of $2^{\pi(n)}\equiv 1\text{ mod }n$, where $\pi(x)$ is the prime-counting function
We denote the prime-counting function with $\pi(x)$ and we consider integer solutions $n\geq 1$ of the congruence $$2^{\pi(n)}\equiv 1\text{ mod }n.\tag{1}$$
Then the sequence of solutions starts as $$...
user243301
4
votes
1
answer
2k
views
Find the Least Prime Divisor of $2^{17}-1$
Show that the least prime divisor of $2^{17}-1$ is $2^{17}-1$ itself.
This question is really anoying. Let $N=2^{17}-1$. What I know is that if $q\mid N$, then $q=34k+1$ for some $k \in \Bbb{N}$ and $...
- 1,502
4
votes
4
answers
150
views
Let $S = \{n\in\mathbb{N}\mid 133 \text{ divides } 3^n + 1\}$. Find three elements of S.
Question:
Let $S = \{n\in\mathbb{N}\mid 133 \;\text{divides} \; 3^n + 1\}$
$a)$ Find three different elements of $S$.
$b)$ Prove that $S$ is an infinite set.
My intuition is find the prime factors of ...
- 272
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
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
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_{...
- 438