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.
4
votes
4answers
80 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...
0
votes
2answers
32 views

How to prove that gcd(k! mod m, m) > 1, for every k > $\alpha$

I'm doing some exercises and I've read that, if $\alpha$ is the first prime factor of a number $m \geq 2$, then, for every $k \geq \alpha$, it is true that $gcd(k!\ mod\ m,\ m) > 1$. I can see ...
0
votes
2answers
23 views

Congruence and GCD relation proof

I came across this theorem: For all integers a,b,c and m>0, if d = GCD(c,m) then ...
1
vote
1answer
22 views

Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
1
vote
3answers
92 views

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$.

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$. E.g. $p(7)=2\cdot3\cdot5$ (and $n=7$ is a solution). Let ...
1
vote
3answers
84 views

Divisibility test for $4$

Claim: A number is divisible by $4$ if and only if the number formed by the last two digits is divisible by $4$. Here's where I've gotten so far. Let $x$ be an $(n+1)$-digit number. So $x= ...
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 ...
3
votes
3answers
65 views

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$ So far I have shown that there is in fact some solution. By the definition of division, $n^2 + 14n +47 = 23k$ Thus, ...
0
votes
2answers
41 views

Question about Divisibility

Suppose we are given the following: $p$ is a prime number; $a, c \in \mathbb{Z}$ and $ n \in \mathbb{N}$. Can I prove that there exists $m \in \mathbb{N} $ and $b \in \mathbb {Z} $ such that ...
0
votes
4answers
131 views

Prove that $53^{53}-33^3$ is divisible by $10$

Prove that $53^{53}-33^3$ is divisible by $10$ I don't know modular arithmetic, so I tried things like that: $53^3 \cdot 53^{50}-33^3=(33+20)^3 \cdot 53^{50}-33^3=(33+20)(33+20)(33+20)\cdot ...
1
vote
2answers
60 views

Number theory proof with modular arithematic [closed]

What is the proof for: If p is an odd prime, show that $$1^n+2^n+3^n+...+(p-1)^n \equiv 0 (\mod p)$$ if $p-1$ does not divide $n$ or $\equiv -1 (\mod p)$ if $p-1$ divides $n$.
17
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
0
votes
1answer
30 views

Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters. Now, I want to choose an integration step such that my step will land on each of the ...
0
votes
4answers
104 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
0
votes
1answer
52 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
1
vote
1answer
42 views

Values of $gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $gcd(a,b)=1$ Then $gcd(a-b,\frac{a^p-b^p}{a-b}) = 0 $ or $ p $ I know that ...
0
votes
4answers
67 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
2
votes
3answers
82 views

Prove that for all odd $n$, there is an $m$ such that $2^m - 1$ is divisible by $n$

I've been trying to solve a problem that reads as such Prove that for all odd positive integers $n$, there exists a positive integer $m$ such that $(2^m) - 1$ is divisible by $n$. Proof by ...
1
vote
1answer
100 views

Remainder problem using MOD

What's the remainder when $ 43^{101} + 23^{101}$ is divided by 66? If we use the remainder obtained when $ 43^{101} + 23^{101}$ is divided by $66$, then it becomes, $$13^{101}+23^{101}$$ then how ...
2
votes
1answer
110 views

If the dividend is multiplied by a given number, and divided by the same divisor, the new remainder is multiplied by the same number?

In a division, if the (the number which is being divided) is multiplied by certain factor and then divided by the same divisor, then the new remainder will be obtained by multiplying the original ...
4
votes
2answers
89 views

Valid Alternative Proof to an Elementary Number Theory question in congruences?

So, I've recently started teaching myself elementary number theory (since it does not require any specific mathematical background and it seems like a good way to keep my brain in shape until my ...
2
votes
2answers
124 views

Chinese remainder theorem issue

Let's say I have the following equations: $$x \equiv 2 \mod 3$$ $$x \equiv 7 \mod 10$$ $$x \equiv 10 \mod 11$$ $$x \equiv 1 \mod 7$$ And I need to find the smallest x for which all these equations ...
8
votes
4answers
625 views

Remainder when $20^{15} + 16^{18}$ is divided by 17

What is the reminder, when $20^{15} + 16^{18}$ is divided by 17. I'm asking the similar question because I have little confusions in MOD. If you use mod then please elaborate that for beginner. ...
2
votes
1answer
883 views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
9
votes
1answer
181 views

Elementary Number Theory; prove existence

Prove that there exists a positive integer $n$ such that $$2^{2012}\;|\;n^n+2011.$$ I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
1
vote
3answers
120 views

Basic Modulo Question

I've been having trouble with this example while studying for my exams. Why is $$2023^{2297}\equiv 20 \pmod{3953}\;?$$ Thanks so much for any help I can get! The examples solves the answer by ...
4
votes
6answers
115 views

Solve $91x\equiv 84\pmod{147}$

So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$. Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
2
votes
4answers
103 views

Proving $x$ is divisible by $20$

I need to prove that $x$ divisible by $20$ if and only if $x=0\pmod4$ and $x=0 \pmod 5$ proving that if $x=0 \pmod 4$ and $x=0 \pmod 5$ than $x$ divisible by $20$ is by the Chinese theorem (am I ...
5
votes
2answers
148 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
0
votes
5answers
187 views

Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
5
votes
4answers
736 views

Show that the difference of two consecutive cubes is never divisible by $3$.

Here is my proof: Let $n \in \Bbb Z$. Then, $n$ is of the form $2k$(even) or $2k + 1$(odd), for some $k \in \Bbb Z$. Without loss of generality (not sure if I can use this), let $n = 2k$. Then, $n ...
1
vote
1answer
68 views

Proving that if $xo + yp = 1$, then $\gcd(o,p) = 1\;$?

I'm currently trying to prove the equation that you see above. I know that it must have something to do with the laws of divisibility, and these rules in conjunction with rules about integers, but ...
2
votes
1answer
96 views

Name of this division property

Let us take two integers, $a$ and $b$. Let us then take $\lfloor a / b\rfloor = c$ and $a \bmod b = d$. Obviously, it follows that $a = bc + d$. Our professor claimed that this was called the ...
7
votes
3answers
353 views

Number of integers not divisible by $p$ and $q$

Here's a part of question from Siklos' "Advanced Problems in Core Mathematics": How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average ...
4
votes
6answers
396 views

Prove that $(n-m) \mid (n^r - m^r)$

In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while ...
0
votes
1answer
66 views

Asociated polynomials

Hi I have another problem..Two polynomials a(x) and b(x) are asociated iff a(x)|b(x) and b(x)|a(x)….Right? And now my problem..And polynomials are indivisible when gcd is asociated with 1..And there ...
3
votes
3answers
786 views

$n^2 + 3n +5$ is not divisible by $121$

Question: Show that $n^2 + 3n + 5$ is not divisible by $121$, where $n$ is an integer.