1
vote
1answer
40 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
1
vote
1answer
27 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
1
vote
4answers
48 views

Problem modulo $p$.

Let $p$ be a odd prime, prove that $1^p+2^p+...+(p-1)^p \equiv 0 \mod p$ I'm not sure how to do this, thanks.
2
votes
2answers
46 views

Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

$$x\equiv a \pmod {100}$$ $$x\equiv a^2 \pmod {35}$$ $$x\equiv 3a-2 \pmod {49}$$ I'm trying to solve this system of congruences, but I'm only familiar with a method for solving when the mods are ...
2
votes
1answer
35 views

Problem on Number of Quadratic Residues

We have two primes $p,q$ and an integer $a$ such that $$\gcd(a,pq)=1$$ How to prove that for the following congruence $$x^2 \equiv a \mod pq$$ either there will be $4$ solutions or $zero$ solutions. ...
1
vote
4answers
40 views

How to find $k$ in $6^{k} \equiv 2 \mod {13}$

Find for which $k$ is $6^{k} \equiv 2 \mod {13}$ I'm having trouble with these types of question in my cryptography class. This is part of Diffie–Hellman algorithm for calculating a shared key. ...
1
vote
2answers
50 views

Determine the last two digits of $3^{3^{100}}$

Determine the last two digits of $3^{3^{100}}$ This is one of the problems in the past exam my modern algebra course. I think I need to use euler-fermat theorem but can't figure out how to use it for ...
1
vote
4answers
52 views

Proving congruence modulo, number theory

The task is to prove $24^{31}\equiv 23^{32}\pmod {19}$. I'm trying to use Fermat's little Theorem and so far I only found that $24^{31}\equiv 19\pmod{19}$. Would proving that $17\mid23^{32}$ prove ...
1
vote
3answers
308 views

Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017). So, this is what I have; By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 ...
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 ...
5
votes
1answer
88 views

remainder of the division of $7^{1203}$ by $143$

I have to find the remainder of the division of $7^{1203}$ by $143$. I thought that I could use the Euler Theorem: Let $a \in \mathbb{Z}$ and $n \in \mathbb{N}$.We also know that $(a,n)=1$.Then ...
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
0answers
46 views

How is 4 a quadratic residue of 7?

On Wolfram's dictionary, it shows that the quadratic residues of 7 are 1,2,4. It shows that the quadratic residues of 5 are 1,4. I tested 1 and 4, and as you can see: $$1^2 = 1 \pmod 5$$ and $$ 4^2= ...
0
votes
1answer
48 views

$x_i=x_{i-1}^2+a\pmod{N}$ with $N$ a composite number.

$x_i=x_{i-1}^2+a\pmod{N}$, $N$ is an odd composite number, assume $N=p \cdot q$ with $p,q$ primes, $x_0=1$ then calculate $\gcd(x_i,N)$, for what $a$ the quadratic iterative function give one factor ...
0
votes
2answers
52 views

Proof that $x^n \mod b = (x \mod b)^n$

I've been messing around with modular arithmetic recently, and stumbled across this, but couldn't find a proof for it anywhere. I hate taking things as truth without knowing why, so could anyone ...
0
votes
1answer
75 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 ...
0
votes
1answer
75 views

Integers $p,q$ such that $pq\equiv 1 \mod (p+q) $

I want to find pair of integers $p,q$ of the form: $$pq\equiv 1 \mod (p+q) $$ What have I tried so far is: Since, $pq \equiv 1 \implies p$ has inverse element with respect to $p+q$. which means ...
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 ...
2
votes
2answers
53 views

$\frac{59}{320} \mod{5}$

The example in the title is just an example really, but I'm wondering how do you calculate $\frac{a}{b} \mod{p}$ when $5 \mid b$, since then $b$ does not have an inverse? Thanks!
5
votes
1answer
290 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 ...
1
vote
1answer
25 views

Is $\sum_{j=1}^{k}a^j \equiv 0 \mod p\;$? where k is the order of $a \mod p$, with $p$ being an odd prime?

In other words is $a^1 + a^2 + \dotsm a^k \equiv 0\mod p\;$? This is true when $a$ is a primitive root of $p$ because $a^1, a^2, \dotsc a^k$ are congruent to $1,2,\dotsc,p-1$ in some order. Hence, ...
3
votes
2answers
136 views

Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or ...
0
votes
0answers
26 views

Suppose y is a prime and that b has order 3 modulo y. What is the order of b+1? [duplicate]

order is 6 by showing the expansion of (b+1)^6, but are there other solutions where I have to solve for all the pairs (y,b) that meets the conditions of the problem ?
2
votes
4answers
111 views

Don't know how to continue modulo reduction

Ok , so the question is to find the last three digits of $2013^{2012}$. After some reduction using Euler's Theorem I got $13^{12}$(mod 1000). I tried dividing it in 8 and 125 and later use the CRT , ...
0
votes
1answer
39 views

Is it true (based on Euler's theorem)

I saw somewhere that by using Euler's Theorem for m=77 we have: "$27^{60}\ \mathrm{mod}\ 77 = 1$ and by using modular exponentiation we also have : $27^{10}\ \mathrm{mod}\ 77 = 1$" For example : if ...
1
vote
1answer
45 views

$p \equiv 5 \mod8\Rightarrow p=(2x+y)^{2}+4y^{2}$

If $p \equiv 5 \mod8$ , then $p=(2x+y)^{2}+4y^{2}$,for some x and y integers. Thanks Here is my approach: I know $p \equiv 5 \mod8\Rightarrow $ $p \equiv 1 \mod4\Rightarrow $ $n^{2}+m^{2}=p\equiv ...
0
votes
1answer
32 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
1answer
82 views

Find period of power sequence $a^k \mod m$, with $a, m$ not coprime

Let $a, m$ be positive integers and $m > 1$. I'm interested in the sequence $(a^k)_{k \in \mathbb{N_0}} \mod m$. Since there are only $m$ different values that can occur in the sequence and since ...
1
vote
0answers
16 views

Sufficient condition for an equivalence

What is a sufficient condition for the equivalence $$ a_1 \uparrow a_2 \uparrow ... \uparrow a_n \equiv a_1 \uparrow a_2 \uparrow ... \uparrow a_n \uparrow a_{n+1}\ mod(\ m)\ ? $$ In a closely ...
0
votes
2answers
53 views

Computing modulus by hand

Can someone please explain how you would compute the following modulus by hand? 7503 mod 81 -7503 mod 81
2
votes
1answer
57 views

Properties of modular arithemtic mod primes and quadratic residues

I have the following two equations: $$z_1 = x_1^2 \pmod p$$ $$z_2 = x_2^2 \pmod q$$ and p and q are prime. and I want to show $x^2$ and $z^2$ are equal mod pq $$x^2 = x_1^2 c_1^2 + x_2^2 c^2_2$$ ...
3
votes
5answers
165 views

Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$?

Does anyone have a intuition or argument or sketch proof of why $\gcd(a,b) = \gcd(b, a \pmod b)$? I do have a proof and I understand it, so an intuition would be more helpful. The proof that I ...
1
vote
0answers
34 views

Lucas Number Equivalent of the Pisano Period?

I'm doing some work with the Pisano Period, and it's leading to also talk about the Lucas numbers $mod \ m$, and their period. Is there a specific notation already designated? Sticking with using a ...
0
votes
1answer
62 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
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 ...
3
votes
2answers
202 views

Calculating $a^n\pmod m$ in the general case

It is well known, that $$a^{\phi(m)}\equiv1\pmod m ,$$ if $\gcd(a,m)=1.$ So, $a^n\pmod m$ can be calculated by reducing n modulo $\phi(m)$. But, for the tetration modulo $m$ $$a \uparrow ...
1
vote
1answer
70 views

How would you compute this modulo problem?

$$ (10^{18}-1)(10^{18}-1) \bmod 10^{18} $$ I am solving a programming problem and I hold my integers in 64 bit long long integers. Above is a particular case I am unable to solve. $(ab)\bmod m = (a ...
0
votes
1answer
56 views

How do modular arithmetic rules hold for modulo with composite numbers?

I know that (x*y)%p = ((x%p) * (y%p))%p holds true for a prime p. Is this equation valid when p is a composite number? How do we write this equation when p is a composite number?
2
votes
0answers
79 views

Fast check If the remainder is 1

Is there any fast method to 'say' that $R = (A \mod B)$ is $1$ or $R > 1$ or $R \neq1$ or $R > k>1$ ( where $k$ is a small integer on $32$ bits) without to actually calculate the real value ...
1
vote
2answers
35 views

Number of elements that exist so $b^3 \equiv a\pmod n$, when n is composed of p and q who are prime numbers

Given $2$ prime numbers,$ p$ and $q$, that are both not even, and $3$ doesn't divide $p-1$ or $q-1$, and $n=pq$, how many elements in $Z^*_n$ exists that has $b$ such that $b^3\equiv a\pmod n$ . I ...
4
votes
4answers
121 views

Solve $x^2+x+3=0$ mod $27$

I was preparing for my Number Theory class for next semester and one of the questions that I came upon is to solve $x^2+x+3=0$ mod $27$. I have seen modular arithmetic before but never one that ...
1
vote
2answers
78 views

Multiplicative inverses for $Z_n$

Whilst reading I came across the strange claim that multiplicative inverses exist for only prime values of $n$ in $Z_n$. I am a little puzzled as contrary to that, I know that additive inverses exist ...
0
votes
2answers
31 views

Does this modular arithmetic equation hold?

Does this modular arithmetic equation hold: $$a_1N_1+a_2N_2+a_3N_3+\cdots+a_mN_m \equiv a_1+a_2+a_3+\cdots+a_m \mod {N_1+N_2+N_3+\cdots +N_m+}$$
0
votes
1answer
21 views

Reducing radical congruence to polynomial congruence

I am trying to find a way to describe all integer values of $x$ for which the following holds true: $\sqrt[2]{(1/2) * x * (x - 1) + (1/4)} + (1/2)\in \mathbb{Z}$ Noting that this can be equivalently ...
0
votes
1answer
18 views

What is the period of $f(X) = (A+K\cdot X) \mod N$

I have a function $f$ mapping from integers to integers as follows: $f(X) = (A+K \cdot X) \mod N$ Where $A,K,X,N$ are positive integers. What is the period of the function?
1
vote
1answer
23 views

Question about prime factorization of remainders

If $x$ mod $m$ = $y$, and we know the prime factorizations of $x$ and $m$, does this tell us anything about $y$?
2
votes
1answer
74 views

Solving system of linear congruences (3 pairs)

So we have the following: $$2x \equiv 3\pmod {5} \\ 3x \equiv 4\pmod {7} \\ 5x \equiv 7\pmod {11}$$ which reduces to: $$x \equiv 4\pmod {5} \\ x \equiv 6\pmod {7} \\ x \equiv 8\pmod {11}$$ Now the ...
3
votes
3answers
63 views

Doubts about a nested exponents modulo n (homework)

As part of my homework I am supposed to find the remainder of the division of $2^{{14}^{45231}}$ by $31$. Using the ideas explained in calculating nested exponents modulo n I tried the following: ...
0
votes
2answers
53 views

Modular Arithmatic

I have been struggling with modular arithmetic, and I would like to try and finally grasp the concept. In particular, solving problems like $7^{30}$ mod 49. I know I will have to use Fermat's Theorem ...