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

learn more… | top users | synonyms

1
vote
2answers
44 views

For positive integers a, b, with b odd, show that $(a+1)\mid (1 + a^b)$.

$(1)$ Let a and b be positive integers and suppose b is odd. Show that $1 + a^b$ is divisible by $a+1$. $\;\quad( $Suggested method is using the geometric sum formula.) $(2)$ Let k be a positive ...
1
vote
6answers
61 views

Positive integers $x$,$y$,$z$

If $x$ , $y$ and $z$ are positive integers and $3x = 4y = 7z$, then calculate the smallest possible value for $x+y+z$. How do you do this? Can someone please give me a hint?
1
vote
5answers
82 views

How can we derive the formula for sum of odd numbers?

We know that $\sum^n_{k=1}(2k-1)=n^2$. Can it be shown using AP?
4
votes
0answers
37 views

Prime number building game

Players $A$ and $B$ choose digits $(0, \dots , 9)$ turn by turn and build number by concatenating the digit they chose to the end of the number. Player $A$ starts by picking the first (one-digit) ...
0
votes
2answers
34 views

How do we solve quadratic congruences such as $X^2+ 3X \equiv -5 \mod{7}$? [duplicate]

How do we solve quadratic congruences such as: $$ X^2+ 3X \equiv -5 \mod{7} $$
1
vote
1answer
42 views

Decompose $ n^n$ in form of prime numbers.?

I want to calculate $n^n$. But the problem is calculating it in simple way is very cumbersome work. So I want to convert it into form $2^a \cdot 3^b \cdot 5^c \ldots$ (prime powers) so that i can ...
1
vote
1answer
49 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...
0
votes
1answer
32 views

How to find $a\mod N $ in a specific way?

Let's I have an integer a and take it's modulo with M (M is a prime Number) which is b. i.e. $b = {a\mod M}$I would like to get $a \mod N$ by doing some operation on operation on b along with M , ...
0
votes
1answer
28 views

Factorization some numbers.

Let $n,m>1$, b is any number. Now, determine: 1) factorization for $b^n-1$ 2) factorization for $b^n +1 $ where $n = 2k+1, k> 0$ 3) factorization for $b^{nm} -1 $ Please give me an advice.
1
vote
0answers
41 views

combinatoric problem - how many …

There is a box with the numbers from 1 to 60 and another box with the numbers from 1 - 60 too. There are 60 students. Each of these students go to both box and pick up a number. If the product of ...
1
vote
1answer
23 views

How do you compute $\frac{p}{qrs} \mod M$?

I would like to find $\frac{p}{q\space \space\space r\space \space s} \mod M $ . As multiplication of denominator can become large .So , $\frac{p}{q\space \space\space r\space \space s} \mod M $ = ...
2
votes
2answers
50 views

remainder when $43$ divides $32002^{4200}$

what will be the remainder when $43$ divides $32002^{4200}$?? what I did is: $32002\equiv10 \pmod{43}$, how to proceed further?
3
votes
1answer
34 views

Euclid's lemma for non-prime numbers.

I was trying to prove that $\sqrt{6}$ irrational as: Let $$\sqrt{6}=\dfrac ab$$ $$\implies a^2=6b^2$$ $$6|a^2 \implies 6|a$$. I should not be able to do the step because 6 is not a ...
0
votes
1answer
28 views

Proof of Hensel's Lemma (particular version)

Let $k\in \mathbb{N}$ and $p$ an odd prime number which do not divide $a$. We suppose that there is a solution $u_k$ to the equation $x^{2} \equiv a [p^{k}]$. Then, there is only one solution ...
-2
votes
2answers
52 views

An integer is divisible by 3 if and only if the sum of the digits is divisible by 3. [closed]

just i can used congruences, An integer is divisible by 3 if and only if the sum of the digits is divisible by 3. thanks..
5
votes
2answers
50 views

Largest subset with no pair summing to power of two

For positive integer $n$, define the set $A_n=\{0,1,\ldots,n\}$. What is the size of the largest subset of $A_n$ such that the sum of any two (not necessarily distinct) elements in it is not a power ...
4
votes
0answers
52 views

$a^2+ab+b^2 \equiv 0 \mod n \iff a\equiv b\equiv 0 \mod n$

Let $n$ be a prime number with $n \equiv -1 \mod 6$ and $a,b$ be positive integers. I want to prove: $$a^2+ab+b^2 \equiv 0 \mod n \iff a\equiv b\equiv 0 \mod n$$
1
vote
3answers
39 views

Parametric solutions to $(4/3)b^2c^2+(4/3)a^2d^2-(1/3)a^2c^2-(4/3)b^2d^2=\square$

Let $a,b,c$ and $d$ be rational.Find a rational parametric solutions for $a,b,c$ and $d$ so that $$(4/3)b^2c^2+(4/3)a^2d^2-(1/3)a^2c^2-(4/3)b^2d^2=\square.$$
2
votes
1answer
27 views

Question about GCD of three integers

Let $a$, $b$, and $c$ be integers with $\gcd(a, b, c) = 1$. Prove that there is some integer $x$ such that $\gcd(a + xb, c) = 1$. I know I should use the Chinese remainder theorem, but I'm still a ...
4
votes
0answers
28 views

Prove: $\lfloor \rho^n + \frac{1}{2} \rfloor $ is divisible by $4$ iff $n$ is odd and divisible by $3$.

Let $\rho$ be the Golden Ratio $$ \rho = \frac{1+\sqrt{5}}{2} $$ Prove that $\rho^n$, rounded to the nearest integer, is divisible by $4$ if and only if $n$ is odd and divisible by $3$. That is, ...
0
votes
3answers
39 views

Show $F_n$ has a least element and it is prime.

let $F_n$ be the set of positive factors of n greater than 1 and $n\in \mathbb{N}$. Show $F_n$ has a least element and it is prime.
4
votes
4answers
51 views

Proving any odd number is a factor of $2^n -1$ for some $n$

I'm struggling with a proof of the following. I feel like it should be a one-liner or something simple but I'm just not grasping the idea: Suppose that m is an odd natural number. Prove that there is ...
2
votes
0answers
12 views

For any integer m show that $\pm m$ is the only associate. [closed]

For any $ m \in \mathbb{Z} $ show that $\pm m$ is the only associate. Thanks!
1
vote
2answers
26 views

Fibonacci divisibility

Prove that the following holds: $3|F_n$ if and only if $4|n$ Base case for $n=1$: $F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4. So the proposition holds for $k=1$ Continue ...
0
votes
0answers
34 views

Generators of $(Z/mZ)^*$

Is the following true? Let $d|m$ be two distinct integers greater than 1. Then the group of units $G:=(Z/mZ)^*$ is generated by $A:=\{ a\in G| a=1$ mod $d\}$ and $\{ b\in G : 0<b< d\}$. And ...
0
votes
0answers
12 views

Question regarding operating modulo on quotient of two numbers

Consider integers $p$,$q$,$r$ and $c$. We know that [($p$*$q$)/$r$] (mod $c$)=[{$p$(mod $c$) * $q$(mod $c$)} * ($r$^(-1)) (mod $c$)] (mod $c$) Now consider en example.Let p=2, q=3, r=3 and c=6. Then ...
0
votes
2answers
103 views

Prepend a 9 or append a 0?

Given a positive integer $x$, will $x$ always be larger if one prepends a 9 in comparison to appending a 0? For x = 1, prepending is largest because $91 > 10$ For x = 9, prepending is largest ...
0
votes
1answer
27 views

How to compute n(mod c) when n(mod a),n(mod b),a,b,c are given?

Given a(prime) > b (prime) > c(any number), is there any way to compute n(mod c) ? n%a,n%b,a,b,c are known.
0
votes
1answer
12 views

Quadratic nonresidues mod p

The question asks to find congruence conditions on prime $p$ such that $7$ is the least quadratic nonresidue mod p. Also, find the least such prime. I solved it for $1,2,3,4,5,6$ mod $p$ and got ...
1
vote
1answer
21 views

Proving q is prime in the Legendre Symbol

Prove that if $p$ is an odd prime and if $q$ is the least integer such that $0$ < $q$ < $p$ and $\left(\frac qp\right)= -1 $, then q is prime. I've tried to solve it by contradiction. I ...
0
votes
1answer
17 views

Problem regarding quadratic reciprocity

Here is the question : Prove that if the prime $p\equiv 1\pmod4$ and $q$ is a quadratic nonresidue mod $p$, then the solutions of the congruence $x^2 \equiv -1\pmod p$ are $x\equiv \pm q^a\pmod ...
0
votes
1answer
17 views

modular multiplicative inverse of $2 \pmod {17}$

Find an inverse of $a$ modulo $m$ for $a=2, m=17.$ Applying euclidian algorithm: $\gcd(17,2)$ $17=8(2)+1$ $2=2(1)+0$ Expressed as a linear combination, this is $1=(1)17-8(2)$, and since the ...
0
votes
1answer
35 views

Chinese Remainder theorem, no inverse?

$x\equiv7(mod 9)$ $x\equiv4(mod 12)$ $x\equiv16(mod 21)$ Compute $m$, $9*12*21=2268$ Compute $M_1=$$m\over3$$=252$ $M_2=189$ $M_3=108$ Here's where i'm struggling. The next step is to get the ...
0
votes
0answers
15 views

Do Sieve Methods all depend on some properties of prime number distribution?

Do Sieve Methods all depend on some properties of prime number distribution to reach any meaningful results ? Particularly, those sieve methods that are used in Goldbach Conjecture. Such as: Brun, ...
0
votes
1answer
22 views

Equality of equivalence classes for congruence modulo 7

Let R be the relation of congruence modulo 7. Which of the following equivalence classes are equal? [35], [3], [−7], [12], [0], [−2], [17] I got 3) [35] = [-7] = [0], [3] = [17], [12] = [-2] ...
0
votes
0answers
15 views

what is the best Schnirelmann Constants?

what is the best Schnirelmann Constant for Goldbach Conjecture ? On http://mathworld.wolfram.com/SchnirelmannConstant.html the best Schnirelmann Constant is 7 ( from Ramaré ) My understanding is ...
0
votes
2answers
35 views

What steps are needed to solve $5x+80 = 13 \pmod 7$ and similar problems?

I am unsure of the steps needed to solve $$5x+80 = 13 \pmod 7$$ or this, $$31x=2\pmod{19}$$ I would like to see the steps necessary.
-1
votes
4answers
44 views

x is divided by 3 and 4 implies its also divided by 6

I want to show that if $[3$ divides $x$ and $4$ divides $x]$ then $[6$ divides $x]$. I guess my starting point is something like $x=3n$ $x=4m$ But how do i show that there is also a $c$ with $x=6c$? ...
-1
votes
1answer
27 views

Finding p in Legendre's symbol

The question is as follows: Find all odd primes $p$ such that $$\left(\frac 7p\right)=1$$ If the Legendre's symbol is flipped by quadratic reciprocity, we get $\left(\frac p7\right)=\pm1$. In this ...
2
votes
1answer
60 views

Statement about divisibility

Let's consider such function: $$f(N) = 1^1\cdot 2^2\cdot 3^3 \dots (N-1)^{N-1}\cdot N^N.$$ Does the expression $$\frac{f(N)}{f(r)\cdot f(N-r)}$$ is always integer? Can you give me any hint about ...
-3
votes
0answers
39 views

Color the balls to satisfy the condition

N balls are kept in a linear fashion all of them are initially not-colored. We have two types of paints RED and BLUE. Now we want to paint the balls such that there are at most 2 positions where a ...
1
vote
1answer
29 views

Use division algorithm to prove for any odd integer n, $n^2 -1$ is a multiple of 8.

Here is what I know if n is any odd integer then $n$ can be expressed as $n=2k+1 ~~~ where~k\in\mathbb{Z}$.So $n^2-1=(2k+1)^2 -1=4k^2+4k=4k(k+1)$ but $k(k+1)~~ is~~even$. Thus $k(k+1)=2t, t\in ...
3
votes
3answers
96 views

How to compute the smallest integer which is sum of cubes in 13 ways?

I would like to know the smallest integer which is sum of three positive cubes in 13 ways, such that $1^3+2^3+3^3=2^3+1^3+3^3$ are same ways of representation? What kind of theory there is behind ...
4
votes
0answers
49 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
2
votes
2answers
87 views

Factoring numbers of the form $11111111$

Why $11111111$ is divisible by $73$? How can we get all the prime factors? It is clear that it is divisible by $11$. Is there any formulae for $1111...11$ ($n$ times)? Give me some idea. Thanks in ...
2
votes
2answers
47 views

Proof That,all the perfect squares each of which is the product of four consecutive odd natural numbers.

It's a question from $BdMO$.It still haunts me a lot. I want to find an answer to this question. Find, with proof, all the perfect squares each of which is the product of four consecutive odd ...
1
vote
3answers
51 views

Finding all prime numbers $p$ such that $p^a + p^b$ is a perfect square

Find all prime numbers $p$ and positive integers $a$ and $b$ such that $p^a + p^b$ a perfect square. How can I find this. I have no idea about this problem.
1
vote
1answer
50 views

The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$.

Prove that for every $n\in \mathbb N$, $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$. I was able to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$ using induction. First, ...
1
vote
1answer
43 views

Find the Value of $n$ Where $15756$ is the $nth$ Member of A Set

It's a question from $BNMO$.It still haunts me a lot. I want to find an answer to this question. Any number of the different powers of $5: 1,5,25,125$ etc is added one at a time to generate the ...
0
votes
5answers
30 views

$x^2+3x+b=0$ has an integer solution (mod $17$) for which $b\lt 17$?

Find all non-negative integers $b<17$ such that the equation $x^2+3x+b=0$ has an integer solution (mod $17$). I know this is probably obvious. But I have no idea what to search for to find the ...