1
vote
4answers
25 views

How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
1
vote
4answers
50 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
4
votes
2answers
84 views

For every integer, some multiple of it is of the form $99 \ldots 900 \ldots 00$

The goal is to prove that for every positive integer $ z$ there exists a positive integer $a$ such that $az = 99 \ldots 9900 \ldots 00$. Let $a = \frac {99 \ldots 9900 \ldots 00}{z}$ That ...
1
vote
2answers
79 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
2
votes
1answer
69 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
3
votes
1answer
59 views

How to show $(n-1)^3n^3(n+1)^3$ is divisible by 7 and 9?

Yeah it looks like a basic, really elementary question, but i'm having hard time with it. First i tried to show that it's divisible by 9 $$(n-1)^3n^3(n+1)^3 = ((n+1)(n-1))^3n^3 = (n^2-1)^3n^3 = ...
1
vote
1answer
39 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
89 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
33 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
31 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
96 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
91 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
81 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
68 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
135 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
65 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$.
18
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
31 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
108 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
53 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
46 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
72 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
83 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
119 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
137 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
101 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
126 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
814 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. ...
3
votes
1answer
1k 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
185 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
139 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
116 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
105 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
172 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
883 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
71 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
98 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
395 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
401 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
67 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
889 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.