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

0
votes
0answers
14 views

Solutions in $\mathbb Q_p$ leads to solution for congruences equations?

Let $p$ be a prime number such that $p\equiv1\pmod 3$. Let $n$ be an integer such that the equation $x^3=n$ has a solution in $\mathbb Q_p$. In fact with our assumptions, the others solution are in ...
0
votes
0answers
25 views

Number of solutions of a difference-of-two-squares congruence with prime moduli

Problem: Show that if $p$ is an odd prime then $p-1$ number of ordered pairs $x, y$(unique modulo p) satisfy $x^2-y^2 \equiv a\mod p$ (for some given $a$ coprime to p). When $a \equiv 0 \mod p$ then ...
0
votes
0answers
28 views

Proving primality of $p$ without making any calculation involving $p$ directly

Wilson's Theorem states that a positive integer $p > 1$ is prime if and only if $(p-1)! \equiv -1 \pmod p$, showing a relationship between factorials and prime numbers. Finding it curious, today I ...
1
vote
0answers
24 views

$p \in \Bbb P, a \in \Bbb N$, then if $ord_p(a)=d$ we have $a^{d-1}+\dots+a+1 \equiv 0 \mod p$.

I want to prove the statement in the title, but I think we need $d \geq 2$ in the statement since otherwise there is a case not fulfilling the statement. My attempt: By assumption we have ...
1
vote
2answers
39 views

Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem. I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod ...
1
vote
1answer
12 views

Why the upper bound on parameters of a Linear Congruential Generator?

The Linear Congruential Generator used as a basis for Universal Hashing is defined by the equation using parameters $a$, $c$ and $m$: $$X_{n+1} = (a\cdot X_{n} + c) \mod m$$ with the following ...
3
votes
2answers
66 views

Show that the cube of any integer is congruent to $0$ or $\pm 1 \pmod 7 $

For any integer, $n$, show that $n^3 \equiv 0$ or $\pm 1(\mod 7)$. Use theory of congruences So I thought about a couple of ways to go with this. I thought about showing $7|n^3$ or $7|n^3\pm1$ to be ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
2
votes
1answer
72 views

Determine all integral solutions of $a^2+b^2+c^2=a^2b^2$

I started like this : $a^2+c^2=b^2(a^2-1)\\c^2 +1=(a^2-1)(b^2-1)$ but it's leads to nowhere. can you help please ?
0
votes
3answers
39 views

Modulo Equations

I am trying to solve a problem involving modulo arithmetic but I am not sure what method to use as I have never done this style of question before nor do I have any examples to work from. The ...
4
votes
3answers
99 views

$1000$th decimal digit of $(8+\sqrt{63})^{2012}$

Find the digit at the $1000$th position at the right of the decimal point of the number $(8+\sqrt{63})^{2012}$ I took this problem from a Mexican Math Olympiad called Galois-Noether. It's the ...
1
vote
3answers
80 views

Congruence $16^{(x^ 2+x+1)} \equiv 4 \mod 11$

Given the congruence $16^{x^2+x+1}≡ 4 \mod 11$ I'm not necessarily sure how to approach this problem if someone can help me head in the right direction since 16 is not a primitive root of mod 11 I ...
-1
votes
2answers
43 views

$x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$ [duplicate]

If $p$ is a prime. Then $x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$. Please explain in the easiest way.
3
votes
2answers
46 views

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$.

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$. I want to know if my attempt is correct. First $a^{13} \equiv (a^3)^4 \cdot a \equiv a^4 \cdot a \equiv a^3 \cdot a^2 \equiv a \cdot a^2 ...
0
votes
2answers
52 views

Find an integer function $f(n)$ that is even for $n\not \equiv 2\bmod 3$, and odd for $n\equiv 2\bmod 3$

Does a function $f:\mathbb{N}\to\mathbb{N}$ that satisfies $$ f(n) \equiv \begin{cases}0 \bmod{2}, & n\equiv 0,1\bmod{3} \\ 1\bmod{2}, & n\equiv 2\bmod{3} \end{cases} $$ exist (with an ...
-1
votes
0answers
24 views

Solutions to a congruence in a product of cyclic groups

I'm trying to answer the following question. How many solution are there for the equation $x\equiv 0 \pmod p$ in $\mathbb{Z}_{p}\times \mathbb{Z}_{p^{3}}\times \mathbb{Z}_{p^{5}}$
2
votes
1answer
21 views

Finding quotient and remainder for a division

We are starting with division and congruence in my algebra course... this is one of the first exercises for the division algorithm. I've done the first that were given with fixed values but now I have ...
2
votes
4answers
62 views

Proving divisibility for $256 \mid 7^{2n} + 208n - 1$

I can't come up with a way of proving this: $$256 \mid 7^{2n} + 208n - 1\\ \forall n \in \Bbb N$$ I've tried by induction but couldn't see when to apply the inductive hypothesis... $$P(n+1) = ...
1
vote
1answer
33 views

Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$

I need help with this problem: Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$. I've got to a point where I know that $n^2 + n + 1 | -21$. So it should be among {${-21, -7, -3, -1, ...
3
votes
1answer
29 views

If for $p \in \Bbb P$ and $x,y,z \in \Bbb N$ we have $x^{p-1}+y^{p-1}=z^{p-1}$, then $p\mid xyz$

I want to prove the statement in the title. This is, how far i came: Proof. We have $p \in \Bbb P$ and $x,y,z \in \Bbb N$ with $x^{p-1}+y^{p-1}=z^{p-1}$. If $p=2$, we have $x+y=z$. Now if $x$ and ...
1
vote
2answers
34 views

How to calculate $x$ in $19^{93}\equiv x\pmod {162}$?

I have to calculate $19^{93}\equiv x\pmod {162}$. All I can do is this,by using Euler's Theorem:- $19^{\phi(162)}\equiv1\pmod{162}$ So,$19^{54}\equiv1\pmod{162}$ Now,I have no idea how to reach ...
0
votes
0answers
26 views

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite?

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite? Is there a general way to determine the number of ...
0
votes
0answers
21 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
2
votes
1answer
34 views

If $p$ is an odd prime show that $2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$

If $p$ is an odd prime show that $$2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$$ This is an exercise from Elementary Number Theory, 2nd Edition by Underwood Dudley. I know that the expression ...
0
votes
0answers
12 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
1
vote
0answers
13 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
0
votes
1answer
23 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n ...
2
votes
1answer
45 views

Corollary to Fermat's Little Theorem

A consequence of Fermat's Little Theorem If $p$ is prime and $a \in \mathbb{Z}$ not divisible by $p$, $a^{p-1} \equiv_{p} 1 $ is If $p$ is prime and $a \in \mathbb{Z}$ then ...
0
votes
0answers
29 views

Use congruence classes to determine the maximum size of a subset of {${1,…,n}$} that has no two numbers differing by $k$.

Given positive integers $n$ and $k$, use congruence classes to determine the maximum size of a subset of {${1,...,n}$} that has no two numbers differing by $k$.
0
votes
1answer
20 views

$n-1 = pq-1 \equiv q-1\pmod{p-1}$ where $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$.

Let $n\in\mathbb{N}$ such that $n=pq$ for two distinct large primes $p$ and $q$. My lecturer simply states that $$n-1 = pq-1 \equiv q-1\pmod{p-1}$$ without any justification and I can't see how this ...
0
votes
2answers
30 views

Number of solutions to $x^2\equiv b \mod p^n$

For an odd prime $p$, and some integer $b,n$. I'm interested in finding the number of solutions to $$x^2 \equiv b \mod p^n$$ Researching this led me into Hensel's lemma but I want to verify I ...
1
vote
2answers
22 views

Confused about a neither statement and modular

I am trying currently in the process of learning proofs involving congruence of integers with methods of direct and contrapositive and proofs with cases. However, I am quite confused by this statement ...
3
votes
3answers
57 views

Prove that $24^{31}$ is congruent to $23^{32}$ mod 19.

According to my knowledge, to prove that $24^{31}$ is congruent to $23^{32}$ mod 19, we must show that both numbers are divisible by 19 i.e. their remainders must be equal with mod 19. Please correct ...
6
votes
1answer
40 views

Can I apply Chinese remainder theorem here?

A number when divided by a divisor leaves $27$ remainder. Twice the number when divided by the same divisor leaves a remainder $3$. Find the divisor. My attempt: Let, the number be=$n$ and the ...
1
vote
2answers
16 views

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. ...
0
votes
2answers
54 views

Determine $x$ if $x = 4 \mod 17$ and $x = 3 \mod 11$. [closed]

Given $x =4\mod 17$ and $x = 3\mod 11$, determine $x$. I know that $\gcd(17,11)= 1$. I was hoping to use this to determine $x$.
3
votes
3answers
83 views

Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

I need to find all the solutions of the congruence $x^2 \equiv 9 \mod 256$. I tried (apparently naively) to do this: $x^2 \equiv 9 \mod 256$ $\Leftrightarrow$ $x^2 -9 \equiv 0 \mod 256$ ...
0
votes
1answer
24 views

Understanding a proof from Rotman's “Advanced Modern Algebra”(Chinese Remainder Theorem)

Please, read this post. I don't need to find any proof of the theorem, a I need to understand a specific step in a stecific proof. This is the proof from J.Rotman's book "Advanced Modern Algebra" 3rd ...
0
votes
1answer
31 views

Why if $a = kb + c$ then $a \text{ mod } b = c \text{ mod } b$

Here is a very simple question in number theory that I can't prove it. If $a = kb + c$, then I would like to know why the following is true ($a,b,c,k \in \mathbb{Z}$): $$a \bmod b = c \bmod b$$ And ...
0
votes
0answers
30 views

Question about the solutions to quadratic congruence $x^2\equiv -1(\mbox{mod}\;p)$

As is known to all, when $p\equiv 1(\mbox{mod}\; 4)$, there are 2 solutions to the congruence in the set $\{1,2,3,...p-1\}$: $$x^2\equiv-1(\mbox{mod}\;p)$$ which to be exact are ...
-2
votes
1answer
36 views

Finding the digit in the units place [closed]

Find the digit in the units place of the number $2009!+3^{7886}$. The options available are: a) $7$ b) $3$ c) $1$ d) $9$
1
vote
1answer
34 views

Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
6
votes
3answers
275 views

Solution to exponential congruence

Is there a clever solution to the congruence without going through all the values of x up to 58?$$2^x \equiv 43\pmod{59}$$ Can I somehow use the fact that $2^4 \equiv -43\pmod{59}$ ?
0
votes
2answers
41 views

Find two pairs of relatively prime positive integers $(a,c)$ so that $a^2+5929=c^2$. Can you find additional pairs with $gcd(a,c)>1$?

This question was asked before, but I was wondering if there's a different approach for this problem. Find two pairs of relatively prime positive integers $(a,c)$ so that $a^2+5929=c^2$. Can you find ...
1
vote
3answers
72 views

What does x equivalent to 2 mod 15 mean?

I came across the following question: Consider the following system of equivalences of integers. $$ x \equiv 2 \bmod{15} $$ $$ x \equiv 4 \bmod{21} $$ The number of solutions in $x$, where $1\le ...
0
votes
3answers
30 views

How do I prove the equivalence of these two congruences? [closed]

I have $7x\equiv 1\pmod8$.How do I prove it is equivalent to $x\equiv 7\pmod8$? I have no idea to start on this question.Thanks for any reply..
0
votes
1answer
12 views

Find an affine linear map given two vectors

Find an affine linear map $$\mathbb{Z}_2^5\to\mathbb{Z}_2^5$$ that sends $(0,1,0,0,1)$ to $(1,0,0,1,0)$. So I know that an affine linear map is one of the form $Az+b$ where $b,z\in\mathbb{Z}_2^5$ ...
2
votes
1answer
23 views

Proof of $a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$

I am currently studying modular arithmetic for a course in cryptography. I have proved many operations, but I am stuck in one: Assume $n,a\in \mathbb{N}$ and $n\ge 2$. Prove that if $\gcd(a,n)=1$ ...
1
vote
2answers
23 views

Help me to understand question on Linear Congruence in simplest and elaborated way.

I came across the following congruence in which I have to get value of $x$. They devide it by $3$ which I understand how and multiply it by $7$ on both sides and proceeds further as shown by photo ...
1
vote
1answer
11 views

Explain this step in solving this system of linear congruences.

I'm looking at this example and it doesn't make sense to me. We have to solve the following systems of linear congruences : $x\equiv 1\pmod 5$ $x\equiv 2\pmod 6$ $x\equiv 3\pmod 7$ We take ...