0
votes
0answers
36 views

Primorial mod $2^{32}$

Is $p_n\#$ (primorial - product of $n$ primes) periodic $\pmod{2^{32}}$? It's periodic $\pmod2$ and $\pmod4$, however it don't seems periodic $\pmod8$ and greater modulus.
4
votes
0answers
190 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
1
vote
1answer
38 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
1
vote
4answers
156 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
0
votes
2answers
128 views

Congruence modulo primes or in a polynomial ring over ${\rm GF}(2)$

Let $p, q$ be primes. Then the linear congruence $$ap \equiv r\pmod q$$ can be solved for $a\in\mathbb Z$ and will have a unique solution for each value of $r$ such that $0\leqslant a<q$. Am I ...
0
votes
1answer
195 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
0
votes
1answer
56 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
1
vote
1answer
36 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
2
votes
2answers
111 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
3
votes
1answer
31 views

Group of numbers in residue number system of first $n$ primes

Denote $$\Pi_n = \Pi_{i=1}^n p_i$$ ie. the product of the first $n$ primes. Assume we have a number $m$. Denote $$L(m) = k \iff \Pi_{k-1} < m \le \Pi_{k}.$$ Assume also $L(1)=1.$ Now, if $L(m) = ...
0
votes
1answer
44 views

question about the forms of prime numbers

I was thinking about primes earlier and I thought of a hypothesis that I have been unable to prove. I was wondering whether it was a known theorem and whether anyone knows a proof or can prove (or ...
0
votes
1answer
23 views

Can diagonalization mod p be generalized to diagonalization mod n?

When you diagonalize a matrix $A$, your $D$ matrix will be the similar to if you diagonalized $A$ mod $p$ (but $D$ will also be mod $p$ in this scenario). I'm having a brainfart moment here. Does $p$ ...
0
votes
1answer
26 views

Find one sum in the function of another sum only

Let $S = s_1 + s_2 + ... + s_n$, with $s_i \in N$. Let $M =(p_1*s_1 + p_2*s_2 + ... + p_n*s_n) \bmod{p_{n+1}}$, where $p_i$ indicates $i$-th prime. Find $M$ in the function of $S$ only. Source: ...
1
vote
1answer
38 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
6
votes
1answer
154 views

Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question. Let $p$ and $q$ be prime numbers. $$5^q\equiv 2^q \pmod p$$ $$5^p\equiv ...
0
votes
0answers
37 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...
0
votes
2answers
27 views

How does one compute how big the cycle of modding by a prime number is?

If I take the $k \in \mathbb{N}$ power of 10 and mod it by a large prime, I notice that the remainders repeat at some point. For instance $10^k mod~7$ seems to repeat every $8$th value of $k$. Given ...
1
vote
2answers
61 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
0
votes
0answers
56 views

Fermat's Little Theorem not useful as $p\rightarrow\infty$

I'm having trouble with some questions of which Fermat's little theorem doesn't seem to simplify enough. For questions such as What is $10^{41} \text{mod}\;49$? I get stuck. Since ...
1
vote
1answer
197 views

Modular exponentiation with Chinese Remainder Theorem

I'm learning modular exponentiation with Chinese remainder theorem. I found a great answer from below ...
2
votes
1answer
61 views

Clarify a problem with prime and composite numbers

What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer? The solution listed says The requested number $\mod {42}$ ...
1
vote
0answers
61 views

Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$. $P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from ...
0
votes
2answers
47 views

Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
0
votes
1answer
130 views

$a ≡ b $(mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$)

Verify that if $a ≡ b$ (mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$), where the integer $n = lcm(n_1 , n_2)$. Hence, whenever $n_1$ and $n_2$ are relatively prime, $a ≡ b$ (mod ...
41
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
1
vote
1answer
51 views

$a$ modulo ${\prod_{i}p_i}$ where $p_i$ are primes.

This may be a very simple question for many of you. But somehow I can not see how to find a good way to answer this. The question is that if it is given that $$a\equiv k_i\mod{p_i},\quad ...
0
votes
0answers
27 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
5
votes
1answer
330 views

A club for some special prime numbers: new members welcome

Given an integer $i$, find an integer $n$ ( $2^{j-1}\le n <2^j$), and a prime divisor $p$ of $M_n=2^n-1$, so that $v= j+i$; where $p$ is written as $k2^v+1$, $k$ odd. In other words, $j$ is such ...
0
votes
1answer
55 views

finding a unique integer using mod

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where ...
1
vote
2answers
122 views

determining order of $x+1$ given the $x$ has order three

I was trying to expand $(x+1)^n$, then plug $x^3$ in to the expansion of the $(x+1)^n$, keep trying it until I get the order, are there any other ways? So if $x^3\equiv 1\pmod y$, how would I ...
1
vote
3answers
96 views

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$.

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$. E.g. $p(7)=2\cdot3\cdot5$ (and $n=7$ is a solution). Let ...
1
vote
0answers
38 views

Identity based encryption

I am implementing ID based encryption in c# right now i am having problem at the following mathematics $$H_1: \{0,1 \}^n \times \{0,1 \}^n \to \mathbb{Z}^*_p, \text{ what does this expression ...
4
votes
1answer
75 views

Carmichael Number

I am little bit confused with the definition of Carmichael Number Wikipedia(http://en.wikipedia.org/wiki/Carmichael_number) saying that Carmichael Number is a composite number satisfies ...
1
vote
2answers
263 views

Prime number test and Fermat's little theorem

We've learn in class that if $a^{p-1} \not\equiv 1 \pmod p$ then $p$ must be a composite number. What is the explanation for that? Thanks!
1
vote
0answers
74 views

Question about tetration modulus a prime $p>100$

Define $x§y$ as the power tower : $x^{x^x...}$ where $...$ means $y$ times. For instance $2§1=2,2§2=4,2§3=16,2§4=2^{16}$. See : http://en.wikipedia.org/wiki/Tetration Let $p$ be a prime larger than ...
1
vote
1answer
65 views

Probabilistic time algorithm for finding the solution for quadratic congruences (case when p is prime)

I was trying to solve the following equation: $$y = x^2 \bmod p$$ where $p$ is prime. I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I ...
2
votes
2answers
53 views

Perfect divisibility for products in modular arithmetic

Say we have that $z^2 - x^2 = 0 \ ( \ mod \ p)$ that implies: $p \ | \ (z-x)(z+x)$ However I was not 100% sure how that implies about the divisibility of p towards $(z-x)$ and/or $(z+x)$ and ...
1
vote
1answer
18 views

A question about $t^x \equiv 1 \pmod {q\#}$ where $t,x$ are integers and $q\#$ is a primorial.

Let $t,x$ be positive integers and $q$ be any prime. I was told that you can solve for $t^x \equiv 1 \pmod {q\#}$ by solving for each prime factor of $q\#$ and then setting $x$ to the least common ...
0
votes
1answer
58 views

Mersenne Primes and Fermat's Little Theorem

This is essentially a two part problem. Prove that $2^{4n+3} = 1$ (mod $8n+7$) with $8n+7$ a prime. Using this prove that $2^{4019} - 1$ is not a Mersenne prime, $4019$ is a prime For ...
3
votes
1answer
66 views

Natural density of primes congruent to m modulo N and to r modulo S

N and S are two different primes. I would like to ask if primes, except N and S, congruent to m modulo N and to r modulo S, gcd(m,N)=gcd(r,S)=1, have natural density 1/φ(Ν)*1/φ(S).
2
votes
1answer
72 views

Proof related with prime numbers and congruence

How to (dis)prove this $ (n-2)! \equiv 1 \mod n$ If n is said to be a prime number. I guess we'll have to use FERMAT’S LITTLE THEOREM, and I just don't know where to start from. Thanks in advance ...
2
votes
1answer
105 views

Meaning of $x^m + y^n = z^r$ (mod $p_1$)

I'm trying to understand how to find a counter example to the Beal Conjecture. One site (here) says that, According to The Prime Pages, the largest primes less than $2^{32}$ are $p_1 = 2^{32}-5$ ...
0
votes
0answers
62 views

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/k} \equiv 1$ (mod n)

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/x} \equiv 1$ (mod n) such that $a^{n-1} \equiv 1$ (mod $n$) and x is prime such as $x |(n-1)$. I am solving the bigger proof ...
-1
votes
1answer
67 views

prime number related proof

I want to prove if following is true for every integer a,b and c $$a^2 - b^2 = cp $$ then p|(a+b) or p|(a-b) where p is a prime number. Any suggestion, help would be highly appreciated. Thanks ...
1
vote
2answers
65 views

Number theory proof with modular arithematic [closed]

What is the proof for: If p is an odd prime, show that $$1^n+2^n+3^n+...+(p-1)^n \equiv 0 (\mod p)$$ if $p-1$ does not divide $n$ or $\equiv -1 (\mod p)$ if $p-1$ divides $n$.
1
vote
1answer
100 views

Primitive Root Proof [closed]

What are the proofs for the following: Let $p$ and $q$ be odd prime numbers with $q=2p+1.$ (a) Prove that $-4$ is a primitive root modulo $q$. (b) If $p\equiv 1\pmod 4$, prove that $2$ is a ...
1
vote
1answer
32 views

How to find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x<p

For a given prime $p$, how do I find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x < p? The problem is that trying thoroughly every $x < p$ is too inefficient. I ...
6
votes
6answers
398 views

How to efficiently compute $17^{23} (\mod 31)$ by hand?

I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with ...
4
votes
2answers
89 views

Twin prime “test” via congruence

I decided to try getting a test for a "twinness" of a prime via Wilson's theorem. Wilson's theorem says that integer $n > 1$ is a prime iff $$(n-1)! \ \equiv -1 \pmod n $$ Now, if both $n$ and ...
0
votes
2answers
222 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...