For questions about congruences in modular arithmetic, concerning for example the chinese remainder theorem, Fermat's little theorem or Euler's totient theorem.

learn more… | top users | synonyms

2
votes
3answers
59 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
0
votes
0answers
14 views

system of congruency prime solutions

If you have a system of congruency and you have the solution space. Is there criteria to determine if there is a prime in the solution space and if yes is there a better way to find them instead of ...
0
votes
0answers
18 views

Reduced Residue class problem

I need to Prove that when $j \ge 3$, then every reduced residue class modulo 2j may be written in the form $((−1)^a)(5^b)$ , where a = 0 or 1 and $1 \le b \le 2^{j−2}$, and in which the integers a and ...
0
votes
1answer
26 views

Prove that $ax \equiv 1 \bmod n \implies \gcd(a,n) = 1$.

I'm trying to prove the following but having difficulties. Suppose $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$ then prove if $ax \equiv 1 \mod n$ then $a$ is coprime to $n$. I know what it ...
1
vote
2answers
27 views

Simple Congruence Problem

-1 is a square modulo an odd prime if and only if that prime is congruent to 1 mod 4. Why is this, I cant seem to figure it out.
2
votes
2answers
23 views

Describe all odd primes p for which 7 is a quadratic residue

I need to describe all odd primes $p$ for which $7$ is a quadratic residue. Now let $\left(\frac{a}{b}\right)$ be the Legendre Symbol. Then if $7$ is a quadratic residue $p$ we must have: ...
1
vote
1answer
33 views

Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$

I tried to solve this equation but without a success: $3x^{2}+6x+1 \equiv 0 \pmod {19}$ I concluded hat $x(x+2)\equiv 6 \pmod{19}$, the only way i think to solve this is by just trying all the ...
1
vote
2answers
56 views

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime.

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime. $(\mathbb{Z} / m \mathbb{Z})^{\ast} =$ unit group modulo $m.$ Suppose that ...
3
votes
5answers
124 views

Solve $x^{2}\equiv 24 \mod 125$

Here's a congruence I'm trying to solve: $$x^2\equiv24 \mod 125$$ What are the techniques I could use to solve it? I know about Euler's phi function, Fermat's little theorem and Chinese remainder ...
0
votes
3answers
47 views

Let $n \in \Bbb N$. Find the inverse of $n \pmod {n + 1}$

Let $n \in \Bbb N$. Find the inverse of $n \pmod {n + 1}$ I tried answering the question and got $n+1 \pmod 1$, is this correct? Do I need to use Pell's equation?
0
votes
2answers
50 views

Find the remainder when $3^{89}7^{86}$ is divided by $17$

Find the remainder when $3^{89}7^{86}$ is divided by $17$. I guess the problem is to be solved by congruencies. But unfortunately, I have no clear conception about it. Can someone please explain ...
1
vote
2answers
30 views

Equality symbols in modular arithmetic

E.g., can I write $(a^{p})^{2p} \equiv a^{2p}=a^pa^p\equiv aa\equiv a^2\pmod{\! p}$? I often see equality symbols inbetween mod equivalences. The equality signs point out the equality is not ...
3
votes
1answer
45 views

Cubic Congruence Solutions

While I was reading a paper on number theory, there was a claim which wasn't prove there and I couldn't find a way to justify it. The claim is as follows For a prime $p$, when $p\nmid a$, the number ...
1
vote
1answer
72 views

Solving to find the general equation with a “mod” equation

They probably aren't called "mod" equation but i couldn't think how else to word them, so I have this equation $8x + 10y ≡ 8 \pmod 7$ And have been tasked with finding the general solution, I know ...
2
votes
1answer
41 views

Use Gauss' Lemma to find Legendre symbol $\left(\frac{-1}{n}\right)$ for $n \equiv 1, 3, 5, 7 \pmod 8$.

I know that if $ n \equiv 1 \pmod 4$, then $\left(\frac{-1}{n}\right)=1$, but in this case we are dealing with mod $8$. If $n \equiv 1 \pmod 8$, then $n=1+8k$. So, $(8k+1-1)/2=4k$. So, we have: ...
1
vote
1answer
50 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
0
votes
1answer
43 views

How to solve congruence modulo equations?

While studying Affine Cipher in cryptography it tells that we need to solve a system of modulo congruence equations. The equations are: $8\alpha+\beta\equiv 15 \pmod{26}$ $5\alpha+\beta\equiv 16 ...
1
vote
1answer
31 views

Let n, k ∈ N. Prove that GCD(n, n + k)|k

Let $n, k\in\mathbb N$. Prove that gcd$(n, n + k)|k$ heres my proof. Is it correct? A proposition in number theory states that gcd$(n,m)$ divides $an+bm$ for all integers $a$ and $b$. A corollary ...
3
votes
4answers
44 views

Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Find the following integers $x$: $x \equiv 7^{57} \mod 133$ I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do ...
3
votes
2answers
72 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
9
votes
3answers
84 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
1
vote
0answers
64 views

$5^x \equiv 1520 \pmod {9797}$ [duplicate]

How do you solve this? What does mod mean and how will I solve it? I understand that it can be solved but how? 5 to some exponent equals the (mod of 9797) what is the answer to this?
-1
votes
3answers
56 views

Number Theory Proof regarding phi [closed]

Let $m =p_1p_2$ such $\gcd(k,\phi(m))=1$ and $kl \equiv 1 \pmod {\phi(m)}.$ Prove that $(a^k)^l \equiv a \pmod m $ even if $\gcd(a,m)$ not equal to $1$.
1
vote
1answer
17 views

Solve linear congruence: $ax + b = y \; (mod \; m)$

I am trying to solve $ax + b = y \; (mod \; m)$ for x, where $a,b,y,m$ are known values. This corresponds to running a linear congruential generator in reverse for one iteration. I am happy to assume ...
3
votes
3answers
67 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
1
vote
1answer
22 views

Check if $n=m^2$ in $\mathbb F_q$

I'm studying elliptic curves in finite fields, and seeing an algorithm to find points of the curve, there's a point in which I have o check if an element $z\in\mathbb F_q$ is a square number, being ...
5
votes
4answers
103 views

What is $3^{43} \bmod {33}$?

I just took math final and one of the question was Find $3^{43}\bmod{33}$. So, I used Euler's function; $\phi(33)=20$. $3^{20}\equiv 1\pmod{\!33}$ By using this fact, I got $27$. One ...
1
vote
2answers
34 views

Solving quadratic or higher degree congruence with very large modulus.

Is there any general way to solve a polynomial congruence with a very large modulus? An example could be $$ x^2-377x+1\equiv 0 \pmod {8683317618811886495518194401279999999 } $$ or $$ ...
-3
votes
1answer
41 views

Show that $1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$ [closed]

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $$1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$$
1
vote
2answers
88 views

Understanding a proof showing that for any prime $p$, there are integers $x$ and $y$ such that $p|(x^2+y^2+1)$.

I asked this question a couple days ago: Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. But I asked it as a guest, and I could not comment on ...
0
votes
2answers
25 views

Solutions of the Congruence

If $x^{10}\equiv 1\pmod{\!55^2}$, how do I know one must have $x^{10}\equiv 1\pmod{\!5^2}$ and $x^{10}\equiv 1\pmod{\!11^2}$?
-1
votes
4answers
45 views

Last 2 digits of a product

What will be the last two digits of $25^{63} \cdot 63^{25}$? The answer is given as $25$ or $75$. What is the procedure to reach this answer?
0
votes
1answer
31 views

Find the set of primes p for which -3 is quadratic residue mod p

Find the set of primes $p$ for which $-3$ is quadratic residue $\text{mod } p$. I have started my solution like this: $1= \left(\dfrac{-3}{p}\right) = ...
0
votes
1answer
35 views

Given $p$ an odd prime, $x^2\equiv a\pmod{p^2}$ and $(a,p)=1$, how could we know that $(x,p)=1$?

If I have the congruence $$x^2 \equiv a \pmod {p^2}$$ where $p$ is an odd prime and $(a,p)=1$, how could I know that $(x,p)=1$?
-1
votes
2answers
51 views

$x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, prove either all three are solvable or exactly one

Let p be an odd prime and a, b ∈ Z with p doesn't divide a and a doesn't divide b. Prove that among the congruence's $x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, either all ...
1
vote
2answers
25 views

Number of solutions to congruences

Is there any general form to determine the number of non-congruent solutions to equations of the form $f(x) \equiv b \pmod m$? I solved a few linear congruence equations ($ax \equiv b \pmod m$) and I ...
2
votes
2answers
104 views

If $ p $ is an odd prime and $ D $ an integer not divisible by $ p $, show that $ x^2 - y^2 \equiv D ~ (\text{mod} ~ p) $ has $ (p - 1) $ solutions.

I am supposed to have proved the following congruence identity: $$ 1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p). $$ This is apparently meant to help me solve the problem stated in ...
2
votes
2answers
34 views

Needing help finding the least nonnegative residue

$2^{47} \bmod 23$ $776^{79} \bmod 7$ $12347369^{3458} \bmod 19$ $5^{18} \bmod 13$ $23^{560} \bmod 561$ I really don't understand how to calculate the ones to powers. Could anyone explain how to ...
1
vote
1answer
48 views

How many solutions to $x^d\equiv a\pmod {p}$?

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$. If $\gcd(d,p-1) > 1$, there are exactly $d$ solutions to $x^d\equiv a\pmod p$. $p$ prime, $d\ge 1$, ...
3
votes
2answers
128 views

Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.

So we obviously we want $ x^{2} + y^{2} + 1 \equiv 0 ~ (\text{mod} ~ p) $. I haven’t learned much about quadratic congruences, so I don’t really know how to go forward. I suppose you can write it as ...
3
votes
4answers
93 views

$5x\equiv3\pmod3$

The answer from class is $x = 3 + 3t$ , $t$ belongs to $\mathbb Z$ I see that: 0 1 2 0 1 2 0 1 2 0 0 1 2 3 4 5 6 7 8 9 Am I understand this right? What is the proper way to find this answer?
3
votes
3answers
81 views

Is $p \equiv q\pmod{15}$ the same as $p\equiv q\pmod{5}$?

Let $p$ and $q$ be prime. If $p\equiv q \pmod{15}$, then is it true to say they are congruent mod $5$? I figure I could say $p - q \equiv 0 \pmod{15}$, so $p\equiv q \pmod{5}$, but what throws me off ...
1
vote
1answer
76 views

Trouble forming general solution for linear congruence

I was given $$ 6x+14y=4 \space \mod 5 $$ I took this approach: $$ 6x+14y-5z=4, \space \text{ for some } z $$ Let $$ w=\frac{6}{(6,14)}x+\frac{14}{(6,14)}y $$ Then, $$ (6,14)w+5z=4 \quad , \quad ...
2
votes
2answers
40 views

If $2^{12^{7}+3}\equiv x \pmod{36}$, then what is the value of $x$?

If $2^{12^{7} + 3} \equiv x \pmod{36}$, then what is the value of $x$? We have: $$ \begin{align} 2^5 & \equiv - 4 \pmod{36} \\ 2^{10} & \equiv 16 \pmod{36} \\ 2^{12} & \equiv - 8 ...
3
votes
3answers
51 views

Number Theory Simple Proof

I am looking at a solution for a problem where the following line is stated but not explained, and I can not seem to make sense of it: If a prime $p\equiv 3\pmod 4$ then why is $\frac{p(p+1)}{2}$ ...
7
votes
2answers
175 views

What is the ten's digit of $7^{7^{7^{7^7}}}$

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already ...
4
votes
4answers
136 views

How to solve $x^3\equiv 10 \pmod{990}$? [closed]

How to solve $x^3\equiv 10\pmod{990}$? It has 3 solutions: 10, 340, 670 (WolframAlpha).
1
vote
3answers
33 views

Basic question about modular arithmetic applied to the divisor sum function $\sigma(n)$ when $n=5p$

While studying the divisor sum function $\sigma(n)$ (as the sum of the divisors of a number) I observed that the following expression seems to be true always (1): $\forall\ n=5p, p\in\Bbb P,\ p\gt ...
6
votes
3answers
233 views

I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but ...
1
vote
1answer
25 views

Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$.

Let $k\ge 1, m\ge 1.$ Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$. First I noticed that the assumption would imply $x^m \equiv 1 \pmod{m^k}$, but that doesn't seem to ...