All Questions
Tagged with prime-factorization modular-arithmetic
93
questions
2
votes
1
answer
71
views
Proof involving modular and primes
My Question Reads:
If $a, b$ are integers such that $a \equiv b \pmod p$ for every positive prime $p$, prove that $a = b$.
I started by stating $a, b \in \mathbb Z$.
From there I have said without ...
- 1,088
2
votes
1
answer
78
views
Large prime divisors in small intervals
For my thesis I would like to find integers (lying in a certain moduloclass) in small intervals which have large prime divisors. And for some reason I decided that I want all bounds appearing in my ...
- 989
0
votes
2
answers
95
views
Show that $2^{84} \pmod{377} \equiv 1 $
$\varphi(377)=336$ and $gcd(377,2)=1$ so $2^{336} \equiv1\pmod{334}$
$84\cdot4=336$
I know that:\begin{cases} & 2^{84}\pmod{13}\Rightarrow2^{12}\equiv 1\pmod{13}\Rightarrow2^{84}\equiv 1\pmod{13}...
- 131
0
votes
2
answers
428
views
Find all $x \in \Bbb Z_{143} $ so $x^{2}\equiv1 \pmod{143}$
$143=11\cdot13$
$\varphi(143)=120$ and $gcd(120,2)=2$
How do I continue?
- 131
1
vote
1
answer
40
views
Find $x$ such that $[x] \neq [0]$, $[x]\in\mathbb{Z}_n$, but $[x]^2=0$.
Find $x$ such that $[x] \neq [0]$, $[x]\in\mathbb{Z}_n$, but $[x]^2=0$. (Here $[x]$ denotes the equivalence class of $x$).
My goal here is to express $x$ in terms of $p$, a prime, and $m$, a natural ...
user322548
-5
votes
1
answer
91
views
Here is a break-down graph of operations done in 4-bit integer multiplication.
The blue nodes represent the number $b = b_3b_2b_1b_0$, and the green nodes represent the number $a = a_3a_2a_1a_0$. The yellow nodes are the output bits after multiplying $a \cdot b$. If $a\cdot b$ ...
2
votes
2
answers
86
views
What is the Least Prime Factor of $3^{3241} + 8^{2433}$
I'm not sure how to do this question
Attempt
$$3^{3241} + 8^{2433}$$
I start by taking this number mod 3
$$3^{3241} + 8^{2433} \equiv 8^{2433} \mod 3$$
No we can see that $8^2 \equiv 1 \mod 3$. So
$$...
- 1,180
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
0
votes
1
answer
642
views
Trailing zeroes in product of numbers with factorial power
I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number.
Assuming $N$ is very large, say $500$, where you cannot find factorial ...
- 235
1
vote
2
answers
52
views
Find the smallest $a\in\mathbb{N}$, so that $a\equiv3\cdot 5^4\cdot 11\cdot 13^3 \pmod 7$
The problem I am trying to solve is:
Find the smallest $a\in\mathbb{N}$, so that $a\equiv3\cdot 5^4\cdot 11\cdot 13^3 \pmod 7$.
I noticed that $3,5,11$ and $13$ are primes, but I've no idea how ...
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
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
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
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\...
2
votes
2
answers
1k
views
Calculating $n$ mod $m$ given the prime factorization of $n$
Say I have the prime factorization of a large integer $n$.
$$n=p_1^{a_{1}}\cdot p_2^{a_{2}}\ldots p_k^{a_{k}}$$
However, I do not have $n$ itself.
How do I calculate $n$ mod $m$, given only $n$'s ...
- 821