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

learn more… | top users | synonyms (1)

2
votes
1answer
49 views

Solve $\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$

Solve $$\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$$ My attempt: $$\gcd (17,23)=1$$ so using the Chinese remainder theorem there is a solution modulo $17\times 23=391$ ...
0
votes
2answers
63 views

Number of positive integer solutions to the equation $(a+b+c)(x+y+z+w) = 15$ [closed]

What is the total number of positive integer solutions to the equation? $$(a+b+c)(x+y+z+w) = 15$$ I could not find a way to solve this algebraically. The way which all other answers are telling i ...
6
votes
3answers
622 views

Find the remainder when a large number is divided by 35.

I don't know why I am wrong with this problem. Here is what I did: The last two digit of $6^{2006}$ is 36. So the answer should be 1. Find the remainder when $6^{2006}$ is divided by 35.
0
votes
0answers
16 views

Number of roots of quadratic polynomial in $ Z/(pq Z) $

I want to prove that quadratic polynomials in $ Z/(pq Z)$ have at most 4 roots, when $ p, q $ are prime. I currently do this by factoring the polynomial, $(x-a)(x-b) $ and then showing that either x ...
2
votes
2answers
47 views

To show that the variables in the system are same in magnitude

I am stuck with this interesting problem, If for non-negative integers $a, b, \text{and} c$, $\frac{a}{b}+\frac{b}{c}+\frac{c}{a}$ and $\frac{b}{a}+\frac{c}{b}+\frac{a}{c}$ are both integers then ...
2
votes
2answers
38 views

Show that for any $a,b\in\mathbb{Z}$, $p$ prime: $(a^p+b^p)^{p^2}\equiv a+b \pmod p$

Show that for any $a,b\in\mathbb{Z}$, $p$ prime: $$(a^p+b^p)^{p^2}\equiv a+b \pmod p$$ Using the binomial expansion, I found that ...
1
vote
3answers
33 views

Show that if $a$ is an integer, $(a^2-a)/2$ is an integer too.

Please help me on this number theory problem. Show that $a\in\mathbb Z$, then $\frac{a^2-a}{2}\in\mathbb Z$.
0
votes
1answer
41 views

Exponential equation possibly with congruences and number theory

$3^x+5^y=a^2$ ($x, y, a$ are non-negative integers) Find all pairs $(x, y)$ which satisfy the equation. I have found the trivial solution $x=1, y=0$, and I have tried with congruences, but it didn't ...
-1
votes
1answer
77 views

Is there a sequence of positive integers such that $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$? [closed]

Can anyone give me a hint on this? Is there a sequence of positive integers such that $(a_{n+3}-a_{n+2})^2=a_{n+1}+a_n$ for all $n$? Or strongly, $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$. If there is, ...
2
votes
2answers
64 views

Prove $1+\frac{1}{\sqrt{\phi^{4n+1}{F_{2n}F_{2n+1}}}+\phi^{2n+1}F_{2n}}=\sqrt{\frac{F_{2n+1}}{\phi{F_{2n}}}}$

$n \ge 1$ $F_n$; Fibonacci numbers $\frac{1+\sqrt5}{2}=\phi$ Prove $$1+\frac{1}{\sqrt{\phi^{4n+1}{F_{2n}F_{2n+1}}}+\phi^{2n+1}F_{2n}}=\sqrt{\frac{F_{2n+1}}{\phi{F_{2n}}}}$$ I can't go any further ...
1
vote
3answers
62 views

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares. I started by: Assume $n=a^2+b^2$ a sum of two squares. Then $a^2,b^2\equiv 0,1,4,7 \pmod9$, and no combination these numbers ...
0
votes
0answers
35 views

Number theory/calculus/algebra etc. equivalents of Euclid's Elements?

Anybody know any books that tackle mathematical topics in a deductive, axiomatic structure akin to Euclid's Elements? Thanks.
0
votes
1answer
12 views

Solving Modular Equations in ${Z_{18}}$ Given Inverses…

I need to solve equations like $5X\bmod 18 = 11$ in ${Z_{18}}$ given their inverses. (The modular multiplicative inverse of 5 being 13 in this case.) How would I do that?
1
vote
0answers
26 views

$p \in \Bbb P, a \in \Bbb N$, then if $ord_p(a)=d$ we have $a^{d-1}+\dots+a+1 \equiv 0 \mod p$.

I want to prove the statement in the title, but I think we need $d \geq 2$ in the statement since otherwise there is a case not fulfilling the statement. My attempt: By assumption we have ...
0
votes
1answer
31 views

Diophantine Equations… $255x + 345y = 60$.

I need to know how to find the general solution by integers to any equation (or identify when there is no such integer solution). The example in my mock exam is $255x + 345y = 60$. I think you need ...
1
vote
2answers
40 views

Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem. I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod ...
1
vote
2answers
39 views

Finding Modular Multiplicative Inverses (Quickly!)

as part of an upcoming number theory exam I will need to find the modular multiplicative inverse of every element of ${Z_n}$ (the ones that exist anyway) very quickly. The only way I know is using the ...
10
votes
4answers
148 views

Prove that $2^n+3^n $ is never a perfect square

My attempt : If $n$ is odd, then the square must be 2 (mod 3), which is not possible. Hence $n =2m$ $2^{2m}+3^{2m}=(2^m+a)^2$ $a^2+2^{m+1}a=3^{2m}$ $a (a+2^{m+1})=3^{2m} $ By fundamental ...
3
votes
0answers
77 views

Partitioning positive integers using digital rivers

I stumbled on a very simple computer science question from the British Informatics Olympiad for schools and colleges. Embedded in it is a very interesting numbers theory problem. Here is the ...
0
votes
1answer
16 views

A certain number when successively divided by $8$ and $11$ leaves remainders of $3$ and $7$, respectively.

A certain number when successively divided by $8$ and $11$ leaves remainders of $3$ and $7$, respectively. What will be the remainder when the number is divided by the product of $8$ and $11$, $88$?
1
vote
1answer
44 views

What the sign ' | ' stand for?

Going through a proof of a theorem, I encountered the following statement: $e\mid a/d$, $e\mid b/d$ Then, $a/d = ex$, $b/d = ey$ where $x,y$ belongs to $\mathbb{Z}$. However, my question ...
7
votes
0answers
195 views

Seemingly easy Diophantine equation $a^3+a+1=3^b$

How to prove that $a=b=1$ is the only positive integer solution to the following Diophantine equation?$$a^3+a+1=3^b$$
3
votes
1answer
60 views

How to compute $(1 \cdot 3 \cdot 5 \cdots 97)^2 \pmod {101}$ [closed]

How to compute $(1 \cdot 3 \cdot 5 \cdots 97)^2 \pmod {101}$ in easiest and fastest way?
1
vote
2answers
33 views

Total number of perfect square which are factors of n [closed]

A number $N$ can be factorized as $$N = p_1^5 p_2^4 p_3^7.$$ Find total number of perfect square, which are factors of $N$.
4
votes
1answer
29 views

On the GCD of two palindromes.

I had an observation. Which I will discuss below. My question will be Is my observation correct? If so, how can one prove it? Observation: Consider the string of palindromes below: $100...01$ and ...
1
vote
1answer
47 views

Do primes “behave” in this way?

Suppose that we choose some real number $\varepsilon >0$. Can we always find $n_0(\varepsilon) \in \mathbb N$ such that for every $n> n_0(\varepsilon)$ there is a prime number $p$ such that ...
0
votes
1answer
65 views

How do I make this formula for the primes more concise?

The form I made for the $(n+1)^{th}$ prime $p_{n+1}$ is $\displaystyle1+\sum_{j=1}^{2p_n-1}\lfloor\frac{p_n!^j}{j!}\rfloor-\lfloor\frac{p_n!^j-1}{j!}\rfloor=p_{n+1}.$ Problem is, just like any ...
0
votes
1answer
24 views

Ιnequality relationship

Let $a,b,c,d$ positive numbers. They are connected with the relations $$b<d,\quad a<c,\quad b<a,\quad d<c$$ Is it possible to prove that $a-b<c-d$?
0
votes
1answer
26 views

$\mathbb{Z}\setminus U$ is open, where U is a basic open set of $\mathcal{B}$, the set of all arithmetic progressions

Let $m, b \in \mathbb Z$ with $m \neq 0$, and $U$ is of the form $Z(m, b) = \{ mx + b \mid x \in \mathbb Z \}$ I'm not sure how to show $\mathbb{Z}\setminus U$ is open, I was thinking to expressing ...
0
votes
1answer
35 views

Euclid GCD intuition

I was reading someone explanation about Euclid's GCD. I understand some things that the person explain but I don't get some points. This is the explanation: If both the large numbers $a$ and $b$ have ...
0
votes
0answers
29 views

A property for a set of integers

Put $$ S=\mathbb{Z}\setminus \{ m^2-n^2: m,n\in \mathbb{Z}\setminus\{0\}\} $$ Conjecture. $S\cap(k+S)\cap(r+S)=\emptyset$, for all $k\in S$ and all $r\in S\cap(k+S)$. Is it true?
3
votes
1answer
117 views

Factors of the numbers of the form $a^2+nb^2$

Let $N=a^2+nb^2$ with $\gcd(a,b) =1$ and $n \in \mathbb{Z^+}$. If $N=xy$ where $x$ and $y$ are relatively prime numbers, in what condition can $x$ and $y$ be also written in the same form as $N$ ...
2
votes
3answers
37 views

Compute the Euler function $\phi(n)$ for $n = 360$ as well as the number of divisors $d(n)$.

Compute the Euler function $\phi(n)$ for $n = 360 $ as well as the number of divisors $d(n)$. Is this correct? $360 = 2^3\cdot 3^2\cdot 5$ thus $\phi(n) = 2^2\cdot 2\cdot 3\cdot 4 = 96$. $d(n) = 4 ...
5
votes
2answers
63 views

Formula for the number of numbers $\le n$ with same prime factors as $n$?

Is there a more concise formula for this? I threw this one together, ...
3
votes
0answers
75 views

Prove that $1^k + 2^k +\cdots+n^k$ is divisible by $1+2+\cdots+n$

This is a problem from Terence Tao's Solving mathematical problems, a personal perspective. The problem is: Let k,n be natural numbers with k odd. Prove that the sum $1^k+2^k+\cdots+n^k$ is divisible ...
1
vote
0answers
21 views

Is there an upper bound for this product over primes?

numberFix a positve real number $X\geq 1$ large enough. Is there an upper bound for this product $$\prod_{y<p\leq X}\left(1+\frac{260}{p}+\sum_{\nu \geq 2} \frac{1}{p^{25\nu/32}}\right)$$ in terms ...
2
votes
1answer
27 views

Find number of Distinct remainders when $2009$ is divided by all natural numbers

Find number of Distinct remainders when $2009$ is divided by all natural numbers. obviously if we divide $2009$ by numbers greater than $2009$ remainder is $2009$ so we have to find remainders when ...
0
votes
1answer
40 views

“Direct” derivation of exponential form of the Riemann zeta function.

There is the identity $$ \zeta(s) = \exp\left(\sum_{n=2}\frac{\Lambda(n)}{\log(n)} n^{-s} \right) $$ for $\Re(s)>1$. Apparently there are quite a few possibilities to derive this. I am out to "try ...
2
votes
3answers
44 views

Get integer solutions for $13x\equiv1\pmod{60}$ by euclidean method

I am now studying the RSA algorithm. The keypair generation equation of RSA is $d*e = 1 \pmod{(n-1)(q-1)}$ (where d, e is public key private key each other) In this situation I got the private key$= ...
0
votes
0answers
29 views

Odd Divisor Numbers in a Range not starting at 1

How can we find, given a range of numbers, how many of those numbers have odd divisors? After some searching, I noticed that perfect squares have this nature only. However, this is only if you start ...
0
votes
1answer
26 views

$x^{(p-1)/d}$ takes d distinct values

Im working on this Exercise I can do do part b) but Im stuck on part c). I know that if $e$ is a positive factor of $p-1$ then the equation: $$X^e \equiv 1 \quad \textrm{mod p} $$ has exactly $e$ ...
1
vote
2answers
67 views

Show that $5\mathbb{Z}-5\mathbb{Z}=5\mathbb{Z}$.

My proof. Lemma. $\mathbb{Z}-\mathbb{Z}=\mathbb{Z}$. Proof. ($\Rightarrow$) Let $z\in \mathbb{Z}-\mathbb{Z}$. Then, there is $z_{1},z_{2} \in\mathbb{Z}$ such that $z=z_{1}-z_{2}$. So, ...
0
votes
0answers
25 views

Mapping between different groups

Given $y = g^x$ $mod$ $p$ (assume we cannot calculate $x$ from $y$), is there a way to find $y'$ s.t., $y' = g^x$ $mod$ $p'$? Is this a DDH problem?
4
votes
1answer
34 views

On factoring and integer given the value of its Euler's totient function.

In an entrance test for admission into an undergraduate course in mathematics the following question was asked. Consider the number $110179$ this number can be expressed as a product of two distinct ...
0
votes
1answer
21 views

Numbers question HCF

P is a positive integer such that it is less than 400. Given that 15 is the Highest common factor of 45 and p , find two possible values of p. This type of my question is my biggest problem . Can I ...
0
votes
1answer
37 views

Finding an upper bound for a sum over primes

Fix $X>\geq 1$ a real number and let $1\leq y<X.$ Is there a positive constant $B$ such that $$\prod_{y<p\leq X} \left(1+\frac{3}{p}+ \sum_{\nu \geq 2} \frac{(\nu+1)^2}{p^{\nu}}\right)\leq ...
0
votes
1answer
62 views

When and why does this divide?

I've been working a lot with forms of this type, $\lfloor\frac{f}{g}\rfloor-\lfloor\frac{f-1}{g}\rfloor=1$ if $g|f$ and $0$ otherwise. This is valid for any expression $f$ and $g$ of natural numbers ...
1
vote
0answers
53 views

Given a group of numbers, get a given value?

I have been thinking about a better solution to the following problem: Given a group of numbers, tell if it is possible to get some value, by multiplying all the numbers by $\{0,1,-1\}$ and then ...
1
vote
1answer
71 views

How do I prove the following result in number theory? [closed]

There exist no $(n, m) ∈ \mathbb{N}$ so that $n + 3m$ and $n ^2 + 3m^2$ both are perfect cubes.
2
votes
2answers
105 views

Express a prime $p$ as $p=a^2-2b^2$

Suppose $2$ is a quadratic residue modulo $p$ for an odd prime $p$. That is, there is an element $u$ such that $u^2 \equiv 2 \pmod{p}$. From here, can we prove that there exist integers $a$ and $b$ ...