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
1answer
9 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
32 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
6 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
0answers
12 views

Prove that there exists integer $k$ such that $m^{e^k}\equiv m\pmod{n}$

Let $n=pq$ for two large primes $p$ and $q$. Let $1<e<\varphi(n)$. Given $m\in\mathbb{Z}_n$, let $c=m^e\pmod{n}$. Prove that there exists a $k\in\mathbb{Z}$, $k>0$ such that $$m^{e^k} ...
0
votes
1answer
18 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
27 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
49 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
36 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
15 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
50 views

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

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
53 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
21 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
29 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
35 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
29 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
261 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
63 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
28 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
19 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
9 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 ...
0
votes
0answers
18 views

Question regarding congruence notation [duplicate]

I have a question regarding notation in modular arithmetic and congruence classes. I am used to the notation $a \equiv b$ $(\mod n)$; it simply means n divides a-b But I've seen a similar notation ...
0
votes
0answers
9 views

Explain following Congruences in elementry way

While studding David M Burton I am felling difficulties with Linear Congruence is there any another way expertise this area (online resources). And how can I show that $21x \equiv 49\ (mod\ 10)$ can ...
1
vote
1answer
32 views

Show that 3 is a primitive root modulo 14. Then, write the other primitive roots modulo 14 in terms of powers of 3. How many are there? [closed]

Show that $3$ is a primitive root mod $14$. Then, write the other primitive roots mod $14$ in terms of powers of $3$. How many are there? A bit lost with this question. Poked around online and ...
0
votes
0answers
27 views

Understanding Fermats Little Theorem

Say I was told to find: $4^{1000} (mod 7)$ Since The modulo is prime, I can use fermats little theorem, now I'm just wondering if my steps are correct: We have that: $4^6 = 1(mod 7)$ //congruent ...
1
vote
3answers
55 views

Is it true: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$

I'm checking the following conjecture: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$. If it is not true counter example would be appreciated. Thanks in advance.
0
votes
3answers
57 views

Solve the following equation in $\mathbb{Z}_{16}$

I have this equation $\hat{5}x = \hat{6}$ in $\mathbb{Z}_{16}$. I'm not good at all at modular arithemetic. So far I just figured it out that $\hat{5}x = 6+16k, k\in \mathbb{Z}$.
0
votes
1answer
15 views

Solving a basic linear congruence

I have been tasked with solving a linear congruence: $$-12x\equiv-3\pmod{26}$$ How do I do this? I've never done linear congruences with minus signs so I'm quite confused. Usually I would find ...
1
vote
1answer
40 views

Suppose that gcd($a,p$) = gcd($b,p$) = 1, and neither of the congruences $x^2 … [duplicate]

Suppose that gcd($a,p$) = gcd($b,p$) = 1, and neither of the congruences $x^2 \equiv a$ mod $p$ or $x^2 \equiv b$ mod $p$ has a solution. Show that $x^2 \equiv ab$ mod $p$ does have a solution. ...
0
votes
2answers
42 views

solve $x^2 -4x +13 \equiv 0 \pmod{81}$?

How do I solve $x^2 -4x +13 \equiv o \pmod{81}$ ? I know that this is the same as $x^2 -4x +13 \equiv x^2 + 2x + 1 \equiv (x +1)^2\equiv 0\pmod{3^4}$ but why is $x \equiv -1\pmod{3}$ the only ...
1
vote
2answers
22 views

Show that if $\gcd(a,pq)=1$ and $g=\gcd (p-1, q-1)$ then $a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$.

Suppose $p\neq q$ are two primes and $g=\gcd (p-1, q-1)$ Show that if $\gcd(a,pq)=1$, then $$a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$$ Hi, how to do? I have no idea how to begin, Thanks.
1
vote
0answers
14 views

Congruences with LCM and Relatively Prime Numbers

How do I verify that if $a \equiv b\pmod{n_1}$ and $a \equiv b\pmod{n_2}$, then $a \equiv b \pmod n$, where the integer $n = \operatorname{lcm} (n_1, n_2)$. Hence, whenever $n_1$ & $n_2$ are ...
0
votes
3answers
29 views

Prove on Theory of Congruences

Prove in elementary way: Prove that if $ab \equiv cd \pmod n$ and $b \equiv d \pmod n$, with $\gcd(b,\ n) = 1$. Then how do I prove that $a \equiv c \pmod n$.
0
votes
0answers
21 views

Use Hensel's lemma to show that if $a^n\equiv 1\mod{p}$ then $\exists b$ $b^n\equiv 1\mod{p^r}$

Let $p$ be an odd prime, and let $n$ be a natural number such that $n\mid p-1$. Suppose $1\neq a\in\mathbb{Z}$ is such that $a^n\equiv 1\mod{p}$, and use Hensel's lemma to show that for any given ...
0
votes
1answer
18 views

Congruent powers implies numbers are congruent

Let $N\in\mathbb{N}$, and let $m,n$ be coprime. Also, suppose $a,b$ are relatively prime to $N$, and that $$ a^n\equiv b^n\mod{N},\ a^m\equiv b^m\mod{N} $$ I need to show that $a\equiv b\mod{N}$. I ...
1
vote
2answers
35 views

Congruence Modulo involving factorials

How do I show that $23!\equiv 21! \pmod{101}$? I tried using a calculator but the numbers are so big that am finding it hard to prove. How can factorials be broken down so that they can be easily ...
0
votes
0answers
17 views

i'm confusing on power of x in modular equation..

From question 1, i thought that fermat's little theorem. a^p≡a ≡b^p ≡ b (mod p ) and because (a,p)=1=(b,p) , (a,p^2)=1=(b,p^2), a^(p^2)≡a≡b≡b^(p^2) mod p^2 but how can we know that a^p≡b^p mod ...
0
votes
0answers
30 views

Let $f \in \mathbb{Z}_p [x]$, where $p$ is prime, be defined by $f(x) = x^p - x$. Show that its Polynomial evaluation is identically zero.

I understand that Fermat's Little Theorem is crucial here, but I am not sure how to tie the whole thing together... Observe: If $f(a) \equiv 0$ then $a^p - a \equiv 0$ for $a \in \mathbb{Z}_p$ ...
1
vote
1answer
33 views

Compute the least positive residue of $3^{83} \pmod {3600}$

Compute the least positive residue of $3^{83} \pmod {3600}$. The group $\Bbb Z_{3600}$ is not cyclic. $3$ is not coprime to $3600$. So I did't know how to compute the congruence without calculator.
0
votes
1answer
38 views

Find the inverses of 2,3,…,16 modulo 17. [closed]

I need to find the inverses of 2,3,...,16 modulo 17 and use to solve (a) 5x ≡ 9 (mod 17); (b) 11x ≡ 3 (mod 17). I found the inverse of 5 modulo 17, to be 7 modulo 17 and know to solve by multiplying ...
0
votes
5answers
73 views

Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by 4

I'm studding D.M Burton & want to solve: Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by $4$. . Please help me by giving your solution to it. I'm new comer to number theory so ...
0
votes
1answer
65 views

Proof checking Number theory: prove that $d\nmid a^{2^{n}}+1$.

Let $a, d, n$ be positive integers with $2<d<2^{n+1}$, prove that $d\nmid a^{2^{n}}+1$. I've made some preliminary observations: I hypothesize that for any $n$, $a^{2^n}+1=2\prod p$ where the ...
1
vote
0answers
22 views

Is there Modular 's cycling property?

Find the number of incongruent solution of the congruence $$x^5+10 \equiv 0 \pmod {11^4}$$ this is problem When I try to solve it, in $\mod 11$, $$x \equiv 1,2,3,4,5,6,7,8,9,10 \pmod{11}$$ ...
2
votes
0answers
71 views

Find polynomial congruent to function modulo 6

How to find polynomial with rational coefficients, which is congruent to given function (or prove that it doesn't exist)? Particularly, how to find $P(x)$, so $$P(x)\equiv ...
0
votes
2answers
43 views

For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$? [closed]

For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$? We are currently covering a section on primitive roots, indices and power residues. I am really lost with this one, any hint/help is ...
3
votes
1answer
54 views

Determine a matrix given two other matrices

Define the following matrices $C,P\in M_2(\mathbb{Z}_{26})$: $$ C=\begin{pmatrix}22&13\\10&2\end{pmatrix},\quad P=\begin{pmatrix}6&21\\8&4\end{pmatrix}. $$ Find an invertible ...