Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
0answers
11 views

Question about properties of congruence

Why can we divide the following expression by 2? $$24u \equiv -2(mod\text{ } 17)$$ $$12u \equiv -1(mod\text{ } 17)$$
1
vote
3answers
42 views

Solve the congruence $6x+15y \equiv 9 \pmod {18}$

Solve the congruence $6x+15y \equiv 9\pmod {18}$ Approach: $(6,18)=6$, so $$15y \equiv 9\pmod 6$$ $$15y \equiv 3\pmod 6$$ So the equation will have $(15,6)$ solutions. Now we divide by 3 $$5y \...
13
votes
1answer
385 views
+500

A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $49$ known examples of even perfect numbers -- on ...
2
votes
2answers
78 views

Finding Pythagorean triplet given the hypotenuse

I have a number $c$ which is an integer and can be even or odd. It is the hypotenuse of a right angled triangle. How can I find integers $a,b$ such that $$ a^2 + b^2 = c^2 $$ What would be the ...
1
vote
0answers
23 views

How to show that for n sufficiently large, relative to k, (n+1)(n+2)…(n+k) is divisible by at least k distinct primes

I would like to show that (n+k)!/n! is divisible by at least k distinct primes whenever n is sufficiently large. We all know that it is divisible by k! and hence by pi(k) ~ k/log k distinct primes, ...
2
votes
1answer
26 views

Suppose $a,b,c > 0$. Then there are finitely many integer $x,y$ with $a^x > cb^y$.

Here is the question: For this question, it says to find finitely many positive numbers pairs of x and y for to fulfill the inequality. My thought is when [A] bigger than 1 or b is smaller than 1, ...
1
vote
0answers
23 views

Is this quantity divisible by $p$?

Let $p$ be a prime. Let $$x_{1} = \binom{2p-1}{p}-1$$ $$x_{2}=\binom{2p}{p+1}-1$$ $$x_{3} = \binom{2p+1}{p+2}-1$$ and $$x_{k}=\binom{2p+k-2}{p+k-1}-1$$I observed that for small values of $p$ $x_{1}$, $...
1
vote
0answers
27 views

Equality of polynomial functions modulo n

Fix positive integers $m$ and $n$. For all polynomial functions $f,g: \mathbb{Z}^m \to \mathbb{Z}$ define the equivalence relation $\sim$ by $$f \sim g \iff \forall x \in \mathbb{Z}^m \ ( \ f(x) \...
5
votes
1answer
166 views

Number Theory Characterization Problem

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...
4
votes
1answer
59 views

Project Euler's, Problem #565

Project Euler's, Problem #565 states: Let $\sigma(n)$ be the sum of the divisors of $n$. E.g. the divisors of $4$ are $1, 2$ and $4$, so $\sigma(4)=7$. The numbers $n$ not exceeding $20$ ...
0
votes
1answer
28 views

Smallest number $n$ for which $p\mid n!+1$ and $n\nmid p-1$

My question is that: What is the smallest positive integer $n$ such that $n!+1$ is divisible by $p$ and $p-1$ is not divisible by $n$ and give some examples for $n$ This is my question, I try to ...
2
votes
2answers
4k views

Proof of Bezout's Lemma using Euclid's Algorithm backwards

I've seen it said that you can prove Bezout's Identity using Euclid's algorithm backwards, but I've searched google and cannot find such a proof anywhere. I found another proof which looks simple but ...
2
votes
1answer
254 views

Why if $a = qb + r$, then $\operatorname{gcd}(a,b) = \operatorname{gcd}(b, r)$ intuitively?

Origin - Elementary Number Theory, Jones, p $5$, Lemma $1.5$ Are there any illustrations? I tried Wikipedia's article and the first picture to the right, but I think this delineates Euclid's ...
2
votes
3answers
38 views

A number theory proof - how do I use these intuitions to prove $c^2 \mid ab$?

I've just been introduced to number theory and I had to admit it's a very cool math subfield. Solving problems is another matter entirely, however. Here is the problem: For positive $a, b, c \in \...
1
vote
1answer
27 views

Number Theory Lemma About Linear Congruence (Explanation Needed)

I was reading Elementary Number Theory Second Edition by Dudley Underwood, and I came across what appeared to me to be a contradiction in chapter/section 5. The book says: If one integer satisfies $...
25
votes
7answers
3k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
2
votes
1answer
42 views

Showing that $c_{i}\equiv 0\pmod{p}$

Let the numbers $c_{i}$ be defined by the power series identity $$\frac{1+x+x^{2}+\ldots+x^{p-1}}{(1-x)^{p-1}}= 1+c_{1}x+c_{2}x^{2}+\ldots$$ Show that $c_{i}\equiv 0\pmod{p}$ for all $i\geq 1$. $\...
1
vote
1answer
90 views

Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$?

How to find the remainder using Fermat's little theorem? Fermat's little theorem states that if $p$ is prime and $\operatorname{gcd}(a,p)=1$,then $a^{p-1} -1$ is a multiple of $p$. For example, $p=...
-1
votes
1answer
28 views

Proof about congruence and gcd

Show that if $gcd(a,b)=1$, then the congruence $ax \equiv k (mod$ $ b)$ has a solution $x$ for every integer $k$ if $gcd(a,b)=1$ then there exists integers x,y such that $$ax+by=1$$ then we multiply ...
14
votes
7answers
4k views

Why is $\gcd(a,b)=\gcd(b,r)$ when $a = qb + r$? [duplicate]

Given: $a = qb + r$ Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so? Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math....
4
votes
7answers
3k views

Prove: $\gcd(a,b) = \gcd(a, b + at)$. [duplicate]

I know that $\gcd(a,b)$ divides $a$ and $b$, and must also then divide $(a)(t)$ ($t$ being some integer). This makes sense to me, but how do I prove it? It seems that the addition of $(a)(t)$ is a ...
2
votes
1answer
32 views

On $\gcd(a-b, (a^n-b^n)/(a-b))$

Let $a,b$ be two coprime integers. Show that the gcd of the numbers $a-b, (a^n-b^n)/(a-b)$ divides $n$ for all $n\in\mathbb{N}$.
2
votes
2answers
90 views

Prove that $\gcd(a, b) = \gcd(a, b + ma)$?

How can I prove that $\gcd(a, b) = \gcd (a, b + ma)$? I have tried this: let $g = \gcd(a, b)$, then $g \mid a$ and $g \mid b$. This means that $g \mid ax+by$. I don't know what to do next. Thanks.
1
vote
6answers
56 views

How to prove $\gcd(a-bc, b) =\gcd(a,b)$ for $a,b,c \in \mathbb{Z}$? [duplicate]

I'm not really sure how to approach the problem, since I'm not really sure I understand the mechanisms why it is true aside from putting some numbers in and see that it works. Qualitatively, I'd try ...
2
votes
5answers
44 views

In how many ways 1387 can written in the sum of $n,(n>2)$ Consecutive natural numbers

In how many ways $1387$ can written in the sum of $n(n>2)$ Consecutive natural numbers? 1.$2$ 2.$3$ 3.$4$ 4.$5$ First we can see that it can be written in the form of the sum ...
2
votes
3answers
61 views

For how many 3-digit prime numbers $\overline{abc}$ do we have: $b^2-4ac=9$?

For how many 3-digit prime numbers $\overline{abc}$ do we have: $b^2-4ac=9$? The only analysis I did is: $(b-3)(b+3)=4ac \implies\ b\geq3 $ $b=3\implies\ c=0\implies impossible!!$ So I deduced that $...
0
votes
3answers
30 views

Question about linear congruences

Consider the congruence $$2x+7y \equiv 5\pmod{12}$$ Here $(2,7,12)=1$. Since $(2,12)=2$, we must have $$7y \equiv 5\pmod{2}$$ Which clearly gives $y \equiv 1\pmod{2}$, or $y \equiv 1,3,5,7,9,11\...
0
votes
3answers
62 views

Non prime number test

Suppose $a\geq 3, n\geq 3$ are integers. I claim that if $gcd(a, n)=1$, then $a^n+n^a$ is not a prime. I am trying find a counter example but till now I did not reach there.
1
vote
0answers
45 views

Prime Number Testing

Suppose $n\geq2$ is an integer. I claim that there is no prime of the form $100^n+1$. I am trying to find a counter example. Till now I did not find such prime. So my question is: Does there exist a ...
7
votes
2answers
263 views

Fermat's Little Theorem and Euler's Theorem

I'm having trouble understanding clever applications of Fermat's Little Theorem and its generalization, Euler's Theorem. I already understand the derivation of both, but I can't think of ways to use ...
0
votes
2answers
46 views

Question about congruence

Find the smallest positive n that satisfies the system of congruences $$n \equiv 3 \pmod 4$$ $$n \equiv 4 \pmod5$$ $$n \equiv 5 \pmod 7$$ Approach: Not very useful $4|3-n$, $5|4-n$, $7|5-n$ $3-...
1
vote
2answers
44 views

Prove the n-th Fibonacci number is less than $2^n$ for all n greater than zero using strong induction

I need to prove the n-th Fibonacci number is less than $2^n$ for all $n \geq 0$ using strong induction. I have been exposed to the idea that strong induction differs from weak induction in that the ...
1
vote
1answer
52 views

Simplify $\frac{1}{1\times2\times3} + \frac{1}{2\times3\times4} +\frac{1}{3\times4\times5}+\cdots+\frac{1}{n(n+1)(n+2)}$ [duplicate]

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with sequencing and series, which yields the shortest, simplest proofs, but ...
6
votes
2answers
5k views

Verifying Carmichael numbers

I'm trying to understand a solution I was given in a tutorial regarding a problem with Carmichael numbers and I was wondering if you guys can help clarify things: A composite number $m$ is called a ...
6
votes
4answers
283 views

How to prove that $4^{2n}-1$ is divisible by $3$ or $5$

My task is to prove that $4^{2n}-1$ is divisible by $3$ or $5$, with $n=1,2,3,...$. Any hints? What is the key observation? Thanks :)
4
votes
1answer
68 views

Find all odd positive integers $n$, which there exists odd positive integers $x_1,x_2,..,x_n$, such that $x_1^2+x_2^2+\cdots+x_n^2=n^4$

Find all odd positive integers $n$, which there exists odd positive integers $x_1,x_2,..,x_n$, such that $$x_1^2+x_2^2+\cdots+x_n^2=n^4$$ My work so far 1) $n=3$ $$x_1^2+x_2^2+x_3^2=81$$ no ...
0
votes
1answer
33 views

Are there more non-perfect square numbers than perfect squares?

Can anything be said on this issue? I was wondering if one can find a mapping such that the cardinality of two sets of perfect and non-perfect squares can be compared. Not sure if it's a good question ...
0
votes
2answers
53 views

What is the largest of the five missing numbers?

This is Q28 from Australian Maths Competition 2014. A circle is surrounded by 6 other circles,in a hexagonal formation.The leftmost circle is 0,which the rightmost circle is 1000.Each of the five ...
0
votes
2answers
31 views

primitive polynomials and their factorisation

A polynomial with integer coefficients is called primitive if its coefficients are relatively prime. For example, $$3{x^2} + 7x + 9$$ is primitive while $$10{x^2} + 5x + 15$$ is not. (a) Prove that ...
0
votes
0answers
14 views

Prove that these pairs of complex numbers have real part 1/2 if they are symmetric in the complex plane.

Let matrix $A$ be defined as: $\Large A(n,k)=k^{-a_k + 1/2 + ib_k}$ if $k$ divides $n$, else $A(n,k)=0$ Let matrix $B$ be defined as: $\Large B(n,k)=\mu(n) n^{a_n+1/2 -ib_n}$ if $n$ divides $k$, ...
0
votes
0answers
25 views

For every prime $p$ and a fixed integer $k$, are there infinitely many values of $n$ such that $p$, $p^n+k$, $kp^n+1$ are all primes?

This is similar to my last question, but may or may not be the case: For every prime $p$ and a fixed integer $k$, are there infinitely many values of $n$ such that $p$, $p^n+k$, and $kp^n+1$ are all ...
2
votes
2answers
25 views

which set is including $k$

$A=\{x^2+k \mid x \in \mathbb Z,-3 \leq x<k\}$, where $k$ is a constant. If $\{6,9\}\subseteq A$, then which set below includes $k$? $\{5x+1\mid x \in \mathbb Z\}$ $\{4x+3\...
0
votes
1answer
64 views

Condition that for a given set of numbers and given divisor all finite sums from this set contain all possible remainders

Given $q \in \mathbb{N}$ and ${a_1, a_2, ...}$ where each $a_j \in \mathbb{N} \cup{\{0\}}$ define $A_p=$ {set of all finite sums of $\{a_1 ... a_p\}$ such that each $a_j$ will appear either $1$ or $0$ ...
1
vote
3answers
56 views

Deciding if a number is a square in $\Bbb Z/n\Bbb Z$

I am looking for a systematic way of deciding if a given number is a square in $\Bbb Z/n\Bbb Z$. E.g. is $89$ a square in $\Bbb Z/n\Bbb Z$ for $n\in \{25,33,49\}$? Brute-forcing it would take too ...
2
votes
1answer
47 views

Does $n\mid(a^n-b^n)$ imply $n\mid(a^n-b^n)/(a-b)$? [duplicate]

Finding my previous question quite naive, I improve my question: Given that $n,a,b \in \mathbb{N}$ and $n\mid(a^n-b^n)$ , can we prove or disprove $n\mid(a^n-b^n)/(a-b)$ ?
0
votes
1answer
49 views

For every prime $p$, are there infinitely many integers $k$, such that $p$, $p+k$, and $kp+1$ are all primes?

Please help me proved or disprove the conjecture below. Thanks. For every (fixed) prime $p$, there are infinitely many integers $k$ such that $p$, $p+k$, and $kp+1$ are all prime? I wasn't exactly ...
4
votes
2answers
46 views

Maximizing product of five-digits numbers

From a French 2016 puzzle and math contest, where no calculator is allowed Using each of the digits $0,1,2,3,4,5,6,7,8,9$ exactly once, find two five-digit integers such that their product is ...
0
votes
1answer
14 views

Number patterns types

Write an expression in terms of n for the nth term in the following sequence $9,16,25,36,49$ The difference is $+ 7 , + 9 , + 11 , + 13, + 15 , + 17 ,$ etc The difference is not constant so it's ...