0
votes
2answers
35 views
0
votes
2answers
17 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 ...
0
votes
0answers
36 views

Primes probability for $2^{2(ak+b)}-3$

I'm working on the following problem: If $x$ is a prime and of the form $ak+b$, is there a possibility to check, whenever $2^{2x}-3$ could be a prime or not, without calculating it or extracting ...
0
votes
0answers
47 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 ...
0
votes
1answer
77 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
45 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
51 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
46 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
74 views

a ≡ b (mod n1) and a ≡ b (mod n2), then a ≡ b (mod n)

Verify that if a ≡ b (mod n1) and a ≡ b (mod n2), then a ≡ b (mod n), where the integer n = lcm(n1 , n2). Hence, whenever n1 and n2 are relatively prime, a ≡ b (mod n1*n2). So I know that if a ≡ b ...
37
votes
5answers
3k 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
49 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
23 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
285 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
51 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
99 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
92 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
35 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
68 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
141 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
58 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
46 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
35 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
53 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
64 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).
1
vote
1answer
63 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
90 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
1answer
28 views

Prove the modular arithmetic proposition

For two distinct prime numbers $p$ and $q$: If $x\equiv 1\pmod{p}$ and $x\equiv 1\pmod{q}$ Show that $x\equiv 1\pmod{pq}$
0
votes
0answers
49 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 ...
-2
votes
1answer
64 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
60 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
84 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
30 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
289 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
72 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
197 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 ...
4
votes
1answer
356 views

An isomorphism that takes Z12 (integers modulo 12 under addition) to Z13* (integers modulo 13 under multiplication)

I'm having a hard time finding an isomorphism that takes the integers in $\mathbb{Z}_{12}$ (those integers modulo 12 under addition) to the integers in $\mathbb{Z}_{13}^{*}$ (those integers modulo 13 ...
3
votes
2answers
120 views

Properties of $x$ that make $x^2 \equiv x+1 \mod p$, where $p$ is prime

Excuse me for putting in a pinch of computer science. For a pre-calculated prime $p$, I need to find all natural $x$ that make $x^2 = x+1 \mod p$. The problem is that trying thoroughly every $x < ...
0
votes
2answers
143 views

What is mod(a,b)?

I was reading the AKS Primality Test. AKS. I could not understand the line : $(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$ What is $\mod{(a,b)}$ in it ?
6
votes
1answer
211 views

Let $F_n$ be a Fibonacci number and $p$ a prime. Verify that for $p \le 61$, if $p\equiv\pm1 \pmod{5}$ then $p\mid F_{p-1}$

Define the Fibonacci entry point of $p$ to be the least integer $n$ such that $p\mid F_n$ So for example, for $p = 3$ - the Fibonacci entry point is $n = 4$ since $F_4 = 3$ and obviously $3\mid 3$. ...
8
votes
1answer
87 views

Prove that $\forall p \in \Bbb P;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$

Prove that $\forall p \in \Bbb P,n \in \Bbb Z^+;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$ and $F_{5^n} \equiv 0 \mod 5^n$, where $\left(\dfrac{5}p\right)$ is the Legendre ...
3
votes
1answer
146 views

Let $p$ be a prime and $q$ a prime divisor of $2^{p} -1$. Use Fermat's Little Theorem to prove that $q\equiv 1 (\mod \space p)$

Question continued: Hint: Consider $ord_{q}(2)$. Similarly, prove that if $r$ is a prime factor of $2^{2^{k}}+ 1 $ then $r\equiv1 (\mod \space 2^{k+1})$ I think I have the first part, however I ...
1
vote
0answers
27 views

Reasoning about $\left\lfloor\frac{p_k\#}{p_{k+1}}\right\rfloor$

This is a follow up question to my previous question. Let $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} ...
1
vote
1answer
23 views

Trying to understand why a set of residues modulo a primorial $p_k\#$ has a range of values smaller than $2p_{k+1}$

I've been reviewing the following: $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} > ip_k\# > ...
3
votes
0answers
64 views

An intuitive interpretation of Montgomery pair corrlation function vs. prime divisibility?

Theorem - If the Riemann hypothesis would be true, and the Montgomery pair correlation conjecture (see linked article page 183-184) true too; let $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal ...
-1
votes
1answer
70 views

Conjecture on limit of $1-(n^{p-1}\mod p)$

Given $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal V_p=1-(n^{p-1}\mod p)$$ let me conjecture that $$\lim_{p\rightarrow \infty}\mathcal V_p = \operatorname{sinc}(2\pi \,n)$$ Question: Is ...
3
votes
1answer
104 views

Length of recurrent strings of numbers in the decimal expansion of $1/p$, where $p$ is prime.

Am I right to assume that: all rational numbers have a recurrent sequence in their decimal expansion, and the length of the expansion of $1/p$, where $p$ is prime, is $p-1$ for sufficiently large ...
4
votes
2answers
88 views

Valid Alternative Proof to an Elementary Number Theory question in congruences?

So, I've recently started teaching myself elementary number theory (since it does not require any specific mathematical background and it seems like a good way to keep my brain in shape until my ...
2
votes
2answers
44 views

Does $((x-1)! \bmod x) - (x-1) \equiv 0\implies \text{isPrime}(x)$

Does $$((x-1)! \bmod x) - (x-1) = 0$$ imply that $x$ is prime?
1
vote
2answers
120 views

What is the distribution of primes modulo $n$?

Let $n\geq 2$ and let $k$ be "considerably larger" than $n$ (like some large multiple of $n$). Then for each $i$ such that $0<i<n$ and $\gcd(i,n)=1$ let's define $$c_i=\left|\{p_j\;|\; p_j\equiv ...