# Tagged Questions

40 views
+50

### Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
83 views

### finding mod of an expression with variables

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 (\bmod 6)$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 (\mod 2)$ so ...
27 views

51 views

### What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
57 views

### Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.
108 views

### An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n}$$ that can be regarder as an analogue of the ...
41 views

### Show that if $a^h ≡ 1\mod p$ then $a^{ph} ≡ 1 \ \mod p^2$.

I don't know how to proceed. I know that regardless of what h is, it divides the order of a modulo $p$. I also know that the order of a divides $\phi(p) \ \text{mod} \ p$, where $\phi$ is Euler's ...
39 views

### x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences?

Say, x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences? I am worried this question is too easy to be true. That is why I am confused. ...
42 views

### Congruence and percentage

Suppose I have three statements of congruence: x = a mod n, y = b mod m, z = c mod p; Furthermore, x is a given percent of x + y + z, as is y and z. Does this uniquely determine x, y, z? Or does it ...
59 views

### Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
186 views

25 views

### Divisibility Method

Is there exist any known method to find divisibility rule of each and every rational number in any numeral system by analysing its reciprocal. And additionally it will give the remainder on division ...
35 views

### $p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
84 views

### What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
254 views

### Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
47 views

### Showing equality of primitive roots with quadratic non-residues.

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of ...
34 views

### Sum of the jumbled digits of $abc_{10}$ is $3194$

In the book that I am reading, the author denotes $abc_{10}$ as $100a+10b+c$ where $a, b, c \lt 10$. So if $a = 3$, $b=2$ and $c=8$ then $abc_{10} = 328$. The author asks the following problem: In ...
32 views

### How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
24 views

### Find all values of parameter A such that two system of congruences are equal

I'm starting to learn some elementary number theory and i came across a task i don't know how to solve. $$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$ and the second one x \equiv A (mod \ ...
31 views

### solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
53 views

### Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube.

Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube. What I have so far: we express the prime factorizations of $35$ and $7$ as $5\cdot7$ and $7$, ...
21 views

### System of equations - modular arithmetic

I am asked to solve the following..... Let $n\in \mathbb{N}$ and suppose that $a,b,c,d,k,l\in\mathbb{Z}$. Consider the system $ax + by \equiv k$ mod $n$ and $cx+dy \equiv l$ mod $n$. Let $D=ad-bc$. ...
73 views

### Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively

Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively. Any hints would be appreciated. Thanks!
32 views

### Solution set to exponential in congruence

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution? It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed? Any hints would be appreciated. Thanks!
27 views

### A form of Chinese remainder theorem

How can we solve equations of the form $c \equiv a \mod b$ for finding the c? Also, sometimes $c$ can be two different numbers, one negative and one positive, when is that possible and how does it ...
51 views

### Find the natural numbers $n$ in which $n^2$ divides $584$? [duplicate]

I'm trying to find the natural numbers $n$ in which $n^2$ divides $584$ ? i tried all the ways i know but i get stuck.
258 views

### Sum of Digits Question

If A is the sum of the digits of $5^{10000}$, B is the sum of the digits of A, and C is the sum of the digits of B, what is C? I know it has something to do with mod 9, but I'm not sure how do use it ...
35 views

### Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
### Verify that $4(29!)+5!$ is divisible by $31$.
Verify that $4(29!)+5!$ is divisible by $31$ I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!