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

learn more… | top users | synonyms

2
votes
1answer
59 views

(i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for $\pi_m(n)$.

Questions: $\pi_m(n)$ is defined as the number of partitions of n in which each part is no larger than m. (i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for ...
9
votes
2answers
116 views

if such$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$ Find this $m$ minimum

let $m,n\in N^{+}$, if such $$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$$ Find the $m$ minimum the value My try: since $$(\sqrt{37}+\sqrt{47})m<n<(\sqrt{43}+\sqrt{41})m$$ ...
0
votes
1answer
114 views

Prove or disprove the following proposition

Prove or disprove the following proposition: There are no positive integers $x$ and $y$ such that $$x^2 - 3xy + 2y^2 = 10$$
9
votes
1answer
177 views

A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in ...
0
votes
3answers
712 views

Square number that is the sum of two squares in two different ways.

I would like to know if a square number exists that can be expressed as the sum of two other square numbers in more than one different way. Also only natural numbers and excluding zero.
3
votes
3answers
79 views

Prove that for all $n\in\mathbb{N}$, $\frac{s(n)}{d(n)}\geq \sqrt n$

Prove that for all $n\in\mathbb{N}$ $$\frac{s(n)}{d(n)}\geq \sqrt n$$ where $s(n) = \sum_{d|n} d$ and $d(n) = \sum_{d|n} 1$. Being honest, study some time arithmetic functions, and can not ...
0
votes
5answers
104 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
0
votes
3answers
231 views

GCD (p+q,p-q) with distinct odd primes

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$.
4
votes
2answers
83 views

Show that $p!$ and $(p - 1)! - 1$ are relatively prime

If $p$ is prime number, with $p>3$ Show that $p!$ and $(p - 1)! - 1$ are relatively prime. I tried $\text{gcd}\;(p!,(p-1)!-1)=d\Longrightarrow d\mid p!$ e $d\mid(p-1)!-1$ having ...
2
votes
1answer
72 views

the sequence 1,11,111,.. and primes

Consider the sequence $\{A_n\} = 1,\, 11,\, 111,\, 1111,\, \dots\,$, where $$A_n = \displaystyle\sum\limits_{k=0}^{n} 10^k$$ I wonder if there exists an $z \in \mathbb{Z}$, such that for all ...
1
vote
2answers
321 views

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r.

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r. I know if $g^k \equiv a\pmod{p}$, then $g^k \equiv a\pmod{p^m}$, but ...
0
votes
0answers
53 views

Let g be a primitive root of m. an index of number a to the base g (written $ind_g a$) is a number t such that $g^t\equiv a \mod(m)$.

Let g be a primitive root of m. an index of number a to the base g (written $ind_g a$) is a number t such that $g^t\equiv a \mod(m)$. Given that $a\equiv b\mod(m)$ and that g is a primitive root ...
3
votes
2answers
138 views

Proving $p\nmid \dbinom{p^rm}{p^r}$ where $p\nmid m$

A question from Advanced Modern Algebra by Joseph J.Rotman. Let $n=(p^r)m $ such that the prime $p\nmid m$.Prove that $p\nmid \dbinom{n}{p^r}$.HINT: Assume otherwise,cross multiply and apply ...
0
votes
1answer
65 views

large numbers - my horse in name the biggest number contest

I read Scott Aaronson's essay Who can name the biggest number and I wonder about a following large number. Take a hundred and apply a factorial function take the result and apply a factorial function ...
3
votes
1answer
114 views

Prove that p is the smallest prime that divides (p-1)!+1

By Wilson's Theorem, we know that p divides (p-1)!+1. Assume there exists another prime d divides (p-1)!+1 and $d<p$. Then $ (p-1)!\equiv-1\mod(d)$. I am not sure if I am right in the following ...
1
vote
0answers
25 views

number of residues modulo $2^n$

I am looking at Walter D. Stangl's paper "Counting Squares in $\mathbb{Z}_n$", and I have a question about the following part of a proof: My question is why must $c \equiv 2^{n-1} \pm b \mod 2^n$? ...
1
vote
0answers
87 views

Need a proofreading why all the units are satisfied $a^2-2b^2 =\pm1$ for $\mathbf{Z}[\sqrt{2}]$

All the units are satisfied Pell's equation $a^2-2b^2=\pm1$ for $\mathbf{Z}[\sqrt{2}]$, $a,b\in\mathbf{Z}$. Here is my proof: Let $a+b\sqrt{2}$ be a unit $\in\mathbf{Z}[\sqrt{2}]$. This implies ...
2
votes
1answer
50 views

Question In Elementary Number Theory Chapter about Euler-Phi.

I have a question about in Euler-phi function chapter in the book 'Elementary Number Theory' by David M. Burton(6th Edition) p.145 exercise number 9. The problem is : Let $f(n)$ be the sum of ...
6
votes
0answers
147 views

number of quadratic residues modulo n

Define $f(n)$ to be the number of quadratic residues modulo $n$. I would like to show that $f$ is multiplicative, that is, for any positive integers $m,n > 1$, $f(mn) = f(m)f(n)$ whenever $(m,n) = ...
0
votes
3answers
63 views

Is it right to say that: if $2a+1=2b$ we have a contradiction?

I am trying to prove by contradiction and I have reached the conclusion that $2a+1=2b$. Now I am tempted to say it's a contradiction and call it a night. Is it a contradiction? because one is even and ...
18
votes
10answers
2k views

How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

How would I prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
1
vote
2answers
40 views

finding large primes

I was wondering if anyone proved about a specific a number that it has to have a prime factor bigger than the currently largest known prime, without specifying how to find this factor, would it be an ...
1
vote
2answers
47 views

Chinese Remainder Theorem with coprime congruences

Suppose that $(a,m)=1$ and $(b,n)=1$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$. Show that if $$ c \equiv a \pmod{m} \\ c \equiv b \pmod{n} \\ $$ then $(c,mn)=1$. I've tried to ...
5
votes
2answers
87 views

Proof that b is not divisible by 6

$$b=\left \lfloor (\sqrt[3]{28}-3)^{-n} \right \rfloor$$ The brackets mean that the number is the largest integer smaller than $(\sqrt[3]{28}-3)^{-n} $ Proof that b is never divisible by 6. I have ...
2
votes
1answer
15 views

Showing an induction step for a congruence relation.

Let $a$ be an odd integer such that $a^{2^{n-2}}\equiv 1\; \mod {2^{n}}$. I want to show that $a^{2^{n-1}}\equiv 1\; \mod {2^{n+1}}$. My try: The integer $a^{2^{n-1}}$ is obtained from ...
3
votes
0answers
40 views

prime factorization of values of $(n+a_1)(n+a_2)\cdots(n+a_9)$

For the 9 distinct positive integers $a_1$, $a_2$, ..., $a_9$, we look at the polynomial $$p(n) = (n+a_1)(n+a_2)\cdots(n+a_9).$$ Prove that for any $a_1,a_2,\dots, a_9$, there exists a number $N$ for ...
1
vote
1answer
20 views

Question about Schnirelmann Density and Sumset: if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, wouldn't $d(A+B)=1$

I've been thinking about the Schnirelmann Density and I think that I may still be confused about SumSet and Density. It seems to me that if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, then $d(A+{B}) = ...
3
votes
2answers
92 views

Find all the positive integer

Find all the positive integers (x,y), such that a) $1!+2!+3!+\cdots+ x!=y^2$ b)$1!+2!+3!+\cdots+x!=y^z$
2
votes
3answers
108 views

I need to prove that the product of two numbers equals the product of their gcd and lcm.

I cant prove it. it's just classic number theory, but it's hard. any help??
0
votes
2answers
47 views

6 is a unique number $n$ such that $n-LD(n)^2 = 2$

Let $LD(n)$ be the lowest divisor of $n$ larger than $1$. Let's find all numbers $n$ such that $n-LD(n)^2 = 2$. If $n$ is even then $LD(n) = 2$ and $LD(n)^2 = 4$. Plugging in we get $n-4=2$, so $n=6$. ...
3
votes
1answer
71 views

Schnirelmann Density: if $d(A) + d(B) \ge 1$, does it follow that $d(A+B)=1$

I am still trying to get my head around the basic properties of Schnirelmann Density. If I'm reading PlanetMath.org correctly, it states that if $d(A) + d(B) \ge 1$, then $d(A+B)=1$ Here's the exact ...
1
vote
4answers
90 views

Common factors for all palindromes

For example a palindrome of length $4$ is always divisible by $11$ because palindromes of length $4$ are in the form of: $$\overline{abba}$$ so it is equal to $$1001a+110b$$ and $1001$ and $110$ are ...
3
votes
3answers
85 views

Why does $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ have new divisors $59$ and $509$ all of a sudden?

I am a noob when it comes to math so please bear with me. Why $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ has $2$ new divisors $59$ and $509$. I mean, all of its divisors are prime factors and ...
1
vote
2answers
135 views

Find all triples of positive integers (x,y,z) such that

Find all triples of positive integers (x,y,z) such that $x^{z+1} \ - \ y^{z+1}=2^{100}$ The RHS is even, then x and y must be odd and $x^{z+1}>y^{z+1}$, but how to find out them all ?
0
votes
1answer
63 views

How to calculate such sums of Legendre symbols?

How to calculate such sums as $\sum_{x\in\mathbb{F}_p} \left(\frac{x^2+ax+b}{p} \right)$ If $x^2+ax+b$has a root, $b$ may be eliminated and the sum is evaluated to be $0+\sum_{x\in\mathbb{F}_p^*} ...
0
votes
0answers
25 views

smallest divisor problem - proof verification

Let LD(n) be smallest divisor of n greater than 1. Let's consider the expression n-LD(n)^2. It can be proven that this expression is positive only for composite numbers. Also 6-LD(6)^2 = 2 The ...
2
votes
2answers
367 views

Relationship between primitive roots and quadratic residues

I understand that if $g$ is a primitive root modulo an odd prime $p$, then Euler's Criterion tells us that $g$ cannot be a quadratic residue. My question is, does this result generalize to prime ...
2
votes
1answer
75 views

Irreducible 3rd degree polynomials over $\mathbb{Z}_3$ field?

I want to find all irreducible polynomials over $\mathbb{Z}_3$ field which have the form $x^3 + a_2 x^2 +a_1 x + a_0$. My thought process: Third degree polynomial is irreducible if it has no roots ...
1
vote
2answers
59 views

How prove this congruence equation has four zeros solution

Question: let congruence equation $$\begin{cases} \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv \overline{a_{m}}(\mod 10)\\ \left(\overline{a_{1}a_{2}\cdots a_{m}}\right)^2\equiv ...
4
votes
2answers
78 views

if $(m,n)=1$ is this true that $(2^m-1,2^n-1)=1$?

if $(m,n)=1$ is this true that $(2^m-1,2^n-1)=1$ ? Observing $2^i-1$'s shows that it seems true! But how to prove it? $2 \rightarrow 3$ $3 \rightarrow 7$ $4 \rightarrow 15$ $5 \rightarrow 31$ $6 ...
1
vote
1answer
55 views

Solving Diophantine equations using modular arithemtic

One common way of showing that a Diophantine equation has no solution is to show that it doesn't have solutions modulo some integer $n$. Such solutions often strike me as being very ad-hoc hence the ...
0
votes
1answer
48 views

An intermediate Modular Arithmetic exercise from AoPS

Let,$D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$ be a nine-digit number consisting of the digits $d_1, . . . ,d_9$,not necessarily all distinct. Let $E=e_1e_2e_3e_4e_5e_6e_7e_8e_9$ be another nine digit number ...
2
votes
1answer
73 views

Finding the all integers solutions (x,y) [closed]

Find all integers (x,y), such that $5x^2-6xy+7y^2=383$
2
votes
1answer
80 views

Let n be a positive integer. Prove that: [duplicate]

Let n be a positive integer. Prove that: $\lfloor \sqrt{n}+\sqrt{n+1}\rfloor=\lfloor\sqrt{4n+2}\rfloor$
1
vote
1answer
61 views

Find all the natural solutions to this diophantine equation

Find all the natural solutions to this diophantine equation $968m =n^2-54257$
2
votes
2answers
70 views

For how many integers $a$ is $\frac{2^{10} \cdot 3 ^8 \cdot 5^6}{a^4}$ an integer?

In Mathleague $11316$ Target #$4$, the question is: For how many integers $a$ is $$\frac{2^{10} \cdot 3 ^8 \cdot 5^6}{a^4}$$ an integer?
3
votes
3answers
72 views

Doubts about a nested exponents modulo n (homework)

As part of my homework I am supposed to find the remainder of the division of $2^{{14}^{45231}}$ by $31$. Using the ideas explained in calculating nested exponents modulo n I tried the following: ...
4
votes
2answers
66 views

How to prove that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$?

Let $a$ be an odd integer and $n$ an integer such that $n\ge 3$. 1) I want to show that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$ 2) Then I want to show that $(\mathbb Z/{2^n\mathbb Z})^*$, the ...
0
votes
2answers
69 views

$6^x \equiv 11 \mod{17}$

Here's a simple question using index notation. Find all incongruent solutions of the following congruence: $$6^x \equiv 11 \mod{17}.$$ Since $3$ is a primitive root modulo $17$, we have $$x ...
2
votes
3answers
72 views

How do you prove set with modulo?

Given any prime $p$. Prove that $(p-1)! \equiv -1 \pmod p$. How to prove this?