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

learn more… | top users | synonyms (1)

2
votes
1answer
52 views

What is an “arithmetic progression”?

Today, while doing my math problems on polynomials, I came across the phrase "arithmetic progression." Despite trying hard, I just can't find out the meaning of this phrase and cannot solve my ...
2
votes
3answers
83 views

Is $p \equiv q\pmod{15}$ the same as $p\equiv q\pmod{5}$?

Let $p$ and $q$ be prime. If $p\equiv q \pmod{15}$, then is it true to say they are congruent mod $5$? I figure I could say $p - q \equiv 0 \pmod{15}$, so $p\equiv q \pmod{5}$, but what throws me off ...
2
votes
2answers
229 views

If $x$ is an integer then $x^2+ 5x - 1$ is odd.

What would be a proof strategy for this? I would like to show a proof of the contrapositive: if the expression is not odd, then $x$ is not an integer. If I go that route, how do I express the ...
2
votes
6answers
93 views

Formally proving that if $x^2 + 1$ is even, then $x$ is odd.

Theorem: If $x^2 + 1$ is even, then $x$ is odd. I have to mention, that I am a beginner at this. So, sorry if it is very wrong. Suppose that $x^2+1$ is even, such that there exists an ...
2
votes
1answer
50 views

Where does this function come from in this proof?

This is an excerpt taken from a proof: Let each $M_n(n\in\mathbb{N})$ be countable, Then there exists an injective function $f_n:M_n\rightarrow\mathbb{N}$. Now, set a function ...
2
votes
3answers
119 views

$a^2 = 2b^3 = 3c^5$ Find the smallest value of $abc$.

We have following equation: $a^2 = 2b^3 = 3c^5$ Where $a, b, c$ are natural numbers. Find the smallest possible value of product $abc$.
2
votes
2answers
45 views

How many distinct numbers can I get mod 8

so I have the following $(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)$ I want to see how many distinct numbers can I get mod $8$ by adding from this list 3 times for example I got so ...
2
votes
2answers
98 views

If sum of seven distinct natural numbers is 100 How to prove that there exist at least one group of three numbers whose sum is 50

There are $7$ distinct natural numbers whose sum is $100$. From these 7 numbers 3 numbers can be selected in $C(7,3)=210$ ways How to prove that at least one of these groups will have sum at least ...
2
votes
2answers
100 views

$a,b,c,p$ are rational number and $p$ is not a perfect cube

Given that $a,b,c,p$ are rational number and $p$ is not a perfect cube, if $a+bp^{1\over 3}+cp^{2\over 3}=0$ then we have to show $a=b=c=0$ I concluded that $a^3+b^3p+c^3p^2=3abcp$ but how can I go ...
2
votes
2answers
42 views

Solving an inequality $B<n!$ without a calculator or gamma function?

Is there a way to solve $B<n!$ where $B$ is some very large real number (suppose for example $B=10^{17}$) without a calculator or gamma function? At the very least, to find the nearest integer for ...
2
votes
2answers
67 views

Prove $10n^8 - 9n^6 - n^2$ is divisible by $45$

Basically, I have to use Euler theorem to prove that $10n^8 -9n^6 -n^2$ is divisible by $45$ So my approach so far is to say $10n^8 - 9n^6 - n^2 = 0 \bmod 45$ Now $45$ can be factored into $5$ and ...
2
votes
2answers
98 views

Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think ...
2
votes
1answer
48 views

Positive rational numbers $a$,$b$ satisfy $a^3+4a^2b=4a^2+b^4$. Prove that $\sqrt{\sqrt{a}-1}$ is also rational.

Positive rational numbers $a$,$b$ satisfy $a^3+4a^2b=4a^2+b^4$. Prove that $\sqrt{\sqrt{a}-1}$ is also rational. My try: $a(a+2b)^2=a^3+4a^2b+4b^2a=4a^2+b^4+4b^2a=(2a+b^2)^2$, so ...
2
votes
2answers
147 views

Number theory research topics

I have to do a project for my number theory class (Undergraduate). The professor asked us to explore a topic from number theory and write about 5 to 10 pages on it. I am a computer science major, so ...
2
votes
1answer
36 views

Show that if $p'=2p+1$ and $p\equiv 3\pmod{4}$, then $2^p\equiv 1\pmod{p'}$

Unsure if this is relevant: In the previous part of the question I deduced that if a number of the form $2^n-1$ is prime (a Mersenne prime), $n$ must also be prime. Question: For primes $p$ and $p'$, ...
2
votes
2answers
66 views

How can I express the ration of double factorials $\frac{(2n+1)!!}{(2n)!!}$ as a single factorial?

How can I change the double factorial of $$\frac{(2n+1)!!}{(2n)!!}$$ to single factorial?
2
votes
2answers
47 views

Suppose that $gcd(a,n)= 1$. Prove that $a^m \equiv 1 \pmod n$ iff $ord(a,n) \mid m$

Here is my attempt. Suppose we have $a^m \equiv 1 \pmod n$ and assume that $ord(a,n) = k$ (order of $a)$ and so since $k = ord(a,n)$ it follows that $k \leq m$ . Now if $k = m$ then we are done but ...
2
votes
1answer
48 views

Contradicting theorems

Let $a,x,y\in\mathbb{Z}$ and $m\in\mathbb{N}$ Theorem 1: If $x\equiv y\pmod{m}$ and $a>0$ then $ax\equiv ay\pmod{am}$ Theorem 2: $ax\equiv ay\pmod{m}\Leftrightarrow x\equiv ...
2
votes
1answer
133 views

Largest integer to divide all products of $n$ consecutive integers

Find the largest integer guaranteed to divide all products of $n$ consecutive integers. I started by looking at small values of $n$. I logically assumed that it should be $n!$. But I couldn't express ...
2
votes
2answers
43 views

Looking for an elementary argument for calculation of $(-1)^{\frac{\phi(p^k)}{2}}$

I got by an queer calculation that for $p$ odd prime these formulas are valid with $\phi(n)$ being the Euler $\phi$-function $$(-1)^{\frac{\phi(p^k)}{2}}=1 \qquad\hbox{if $p\equiv 1\mod 4$} $$ and ...
2
votes
1answer
90 views

Which integers can be written in two different ways as a sum of $n$ distinct factorials?

Problem 11 from the 1966 IMO Shortlist asks: Does there exist an integer $z$ that can be written in two different ways as $z = x! + y!$, where $x$, $y$ are natural numbers with $0 < x \leq y$? ...
2
votes
2answers
62 views

Show that $x^4 \equiv -1\pmod p $ is solvable $\iff $ $ p \equiv 1 \pmod 8$

Show that $x^4 \equiv -1 \pmod p $ is solvable $\iff $ $p \equiv 1 \pmod 8$ My attempt : $p$ must satisfy $(-1)^{(p-1)/d}\equiv 1 \pmod p$, where $d = \gcd(4,p-1)$ but I still don't see how this ...
2
votes
1answer
43 views

Solving diophantine equation $6x+9y=1050$ where $x,y \in\mathbb{N}$

I have to solve this Diophantine equation: $6x+9y=1050$, where $x,y \in\mathbb{N}$. I am not sure as to how to solve this for only the whole numbers, but I think I'm doing it right. I used the ...
2
votes
1answer
103 views

Are there 3D geometric proofs of Fibonacci identities?

There is a significant number of identities involving Fibonacci numbers that can be proven in a sort of geometric way, as it is shown in the following picture: However, I couldn't find any such ...
2
votes
3answers
109 views

Possible not countable extension of the natural numbers?

This question comes from:Is $1234567891011121314151617181920212223......$ an integer? We define $\mathcal{A}$ as the set of infinite strings of digits $$ \bar a_i=a_0 a_1a_2a_3\cdots a_i \cdots ...
2
votes
2answers
63 views

Find the least number b for divisibility

What is the smallest positive integer $b$ so that 2014 divides $5991b + 289$? I just need hints--I am thinking modular arithmetic? This question was supposed to be solvable in 10 minutes...
2
votes
5answers
117 views

Testing integrality of a number

Let $x$ be a real number. Show that $x$ is an integer if and only if $$[x] + [2x] + \cdots + [nx] = n ([x] + [nx])/2,$$ for all natural numbers $n$. Can you give me an idea?
2
votes
1answer
47 views

compute $ 2^{1212} $ mod $2013$

Condition: Using Fermat's Little Theorem We get $ 2^{2012} \equiv 1 $ mod $2013$ Hence $2^{1006} \equiv 1 $ mod $2013$ But I can't seem to go further than here...any suggestions?
2
votes
2answers
78 views

Positive integers $n$ which can be written as $x^2-3y^2$

My problem is: Which positive integer $n$ can be expressed in the form $x^2-3y^2$? First I consider the equation $$x^2-3y^2=p$$ with $p>2$ is a prime. By quadritic residue, notice that ...
2
votes
1answer
67 views

For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$. I have no idea how to prove that.
2
votes
1answer
48 views

Finding solutions of a 2-variable biquadratic equation

Find all integral solutions of $$y^2+y=x^4+x^3+x^2+x$$ Factoring both sides we get $$y(y+1)=(x^2+x)(x^2+1)$$ Let $Y=y+1/2$ and $X=x^2+\frac {x+1}2$. Therefore $$(Y+1/2)(Y-1/2)=(X+\frac{x-1}2)(X-\frac ...
2
votes
1answer
74 views

Question about $2p-1$ and $2p+1$, where $p$ is a prime.

Let $x+1$ be any prime greater than $3$. By Bertrand's Postulate, there is at least one prime between $\frac{x}{2}$ and $x$. Let $\{p_1,p_2,\dots, p_n\}$ be the primes between $\frac{x}{2}$ and ...
2
votes
3answers
261 views

Natural numbers in set theory is {0,1,2,…}?

The set of natural numbers $\mathbb{N}$ in set theory is defined with the axiom of infinity as the smallest inductive set and then it is usually proven that $\mathbb{N}$ satisfies the Peano axioms and ...
2
votes
1answer
73 views

Number of solutions of $3x^2 - 5x + 3\equiv 0 \pmod{m}$?

I'm asked, for each of the following values of $m$, to find the number of solutions (in the set $Z_m$) of the quadratic congruence $3x^2 - 5x + 3\equiv 0 \pmod{m}$. For $m=53$ $m=73$ ...
2
votes
1answer
48 views

If $p,q$ are prime numbers prove that $p=q^2+q+1$.

Prove that if $p$ and $q$ are prime numbers such that $p|q^3-1$ and $q|p-1$ then: a) $p|(q^2+q+1)$ b) $p=q^2+q+1$ It is easy to prove part a but I am having troubles with part b. Does anyone have ...
2
votes
3answers
165 views

Showing there is no natural number between two consecutive natural numbers

I want to show that: $x\subset S(x)$ where $S$ is the Successor function and $\not\exists z:x\subset z\subset S(x)$ These are obvious results, but the relation of $m<n\iff m\in n$ is given as a ...
2
votes
1answer
259 views

Does the congruence $x^2 - 3x - 1 \equiv 0$ (mod 31957) have any solutions?

Does the congruence $x^2 - 3x - 1 \equiv 0$ (mod 31957) have any solutions? (A hint given is that I can use the quadratic formula to find out what number you need to take the square root of modulo ...
2
votes
2answers
101 views

$(a,b)[a,b]=ab$ in non factorial monoids

Do you know of a proof of $[a,b](a,b)=ab$ in $\mathbb Z$ that doesn't use prime factorization? To be more precise let's strip all unnecessary properties and leave only the bare bones of divisibility: ...
2
votes
1answer
41 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
2
votes
2answers
58 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
2
votes
1answer
79 views

Integer solutions to $a^4+b^7=11^{11}$

Determine the solution set of $a^4 + b^7 = 11^{11}$ with $a,b \in \mathbb{Z}$. Hints would be appreciated. I have tried working modulo $5$ and have deduced that $a$ or $b$ must be multiples of ...
2
votes
1answer
93 views

computing $29^{25}$ (mod 11)

I'm trying to learn how to use Fermat's Little Theorem. $29=2\cdot11+7 \Rightarrow 11\nmid29$ by the theorem we have $29^{10}\equiv 1$(mod 11) $25=10\cdot 2 + 5$ $ ...
2
votes
2answers
41 views

How calculate the under sum of numbers

How calculate the under sum of numbers $$\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{6}+\cdots+\dfrac{1}{100}=?$$ I think on it a lot. But i can not find a easy answer.
2
votes
3answers
56 views

An equivalent definition of the modulo relation

Let $k$ be a fixed positive integer. Define binary relation $R$ as follows: $$ (n,m) \in R \iff k\mid (n-m) $$ Then show that $(n,m) \in R \iff n$ and $m$ have the same remainder when you divide ...
2
votes
1answer
52 views

Find all positive integers $n$ such that

$3^n+22^n$ is a perfect square. Obviously $n=1$ is an answer but i'm not sure how to show that there aren't infinite solutions.
2
votes
1answer
78 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 ...
2
votes
1answer
80 views

Can any root, such as a square root or a cube root, be rational?

I've heard of this and most roots are irrational such as $\sqrt{8}$ and $\sqrt[3]{25}$. So, can any of these roots be rational? I think so as I'm typing this. I think these are rational: ...
2
votes
1answer
228 views

Proof of Euler's Totient Theorem

I have seen quite a few proofs of Euler's Totient Theorem that $a^{\phi(n)}≡1 \pmod n$ for all $a$ relatively prime to $n$. However, none have been done using induction. That is what I have been ...
2
votes
1answer
43 views

Basic question: what does this mean: polynomial $f(x) \in \mathbb{Z}[x]$ has a root mod $d$?

What does "A polynomial with coefficients in $\mathbb{Z}$ has a root of mod $d$" mean? I'm not quite sure what this means, my search has led me to a few slightly different answers. I'd love to see an ...
2
votes
1answer
38 views

If $a^{8}+a^{7}-a^{5}-a^{4}-a^{3}+a+1= mn$ then $m\equiv n\equiv 1 \pmod{15}$

How to prove: in integers for any $a$ If $$a^{8}+a^{7}-a^{5}-a^{4}-a^{3}+a+1= mn,$$ then $$m\equiv n\equiv 1 \pmod{15}.$$ ?