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

learn more… | top users | synonyms (1)

6
votes
3answers
125 views

My formula for sum of consecutive squares series?

I stumbled upon a specific series, who's Sum of squares of consecutive integers equals the sum of squares of the continuation of that consecutive integers. For exmaple, this first number in the ...
-2
votes
0answers
41 views

Prime number theory. [closed]

If $a$ is coprime to $b$ and $y$ and $b$ are both coprime to $x$; then Prove that $ax+by$ is a coprime to $ab$.
-1
votes
1answer
45 views

Conjecture: Partitioning $\Bbb N$ into parts that sum to $13^i$ [closed]

Recently I was thinking and came up with a conjecture that goes as follows: Conjecture: There exists a $\Omega$ such that $$\Omega = \Bigg\{A_i \ \Bigg| \ \forall i,j:i\not=j, \ A_i\cap ...
0
votes
1answer
34 views

There exists an irrational number z such that x<z<y

I know there are lots of post about this but I wanted to know this proof would work also. Proposition. Let $x,y ∈ \mathbb{R}$ with $x < y$. There exists an irrational number $z$ such that $x < ...
1
vote
0answers
28 views

The Divisors of $s(2s+1)$ and Primes $n$, $4n+1$, and $6n+1$

This question is somewhat related to this one. Most of this is by way of a computer search: claim: If $s$ is any positive integer I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be the divisor ...
3
votes
3answers
63 views

Let $A = (0,1]$. Then$\text{ inf}(A) = 0$

I posted before about this proposition and I thought I got it right but then I was told that it is still wrong so I am really confused again.. Here is my proof Proof : Let $A = (0,1]$ Here, since ...
3
votes
1answer
28 views

How to prove that if the sum of the totatives of two numbers is equal then the numbers are equal?

As the title says, I am trying to prove that if the sum of the totatives of $a$ equals the sum of the totatives of $b$ then $a = b$ but I am stuck. I have that sum of totatives of $n = f(n)= ...
3
votes
1answer
38 views

Solving $(ap)^2-d(bq)^2=1$ for distinct primes $p,q$

I'm pondering the following claim regarding special cases of the Pell equation. Conjecture: For every pair of distinct primes $p$ and $q$, there exist integers $a$ and $b$, and a non-square integer ...
2
votes
2answers
26 views

Proving that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\ (mod\ p)$

How can I prove that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\pmod p$?
1
vote
2answers
41 views

Number of integral solutions for an equation

How do we approach this kind of problem of finding number of positive integral solutions to $$\frac{1}{x}+\frac{1}{y} = \frac{1}{n!}$$ Here $n$ is given.
0
votes
0answers
29 views

If $k(a^2+mb^2) = c^2+md^2$, what can be said about the form of $k$?

Let $k,a,b,c,$ and $d$ be integers, and let $m \ge 2$ be a non-square integer, such that $$ k(a^2+mb^2) = c^2+md^2. $$ QUESTIONS: What can be said about the form of $k$ with no further ...
1
vote
0answers
21 views

Number of integral solutions of $x_1.x_2.x_3=x$

Let $x$ be the element of the set $A=\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$ and $x_1, x_2, x_3$ be positive integers and $d$ be number of integral solutions of $x_1.x_2.x_3=x$ , then $d$ is ...
6
votes
1answer
105 views

Does rationality of $\cosh(nx)$ and $\cosh((n+1)x)$ imply rationality of $\cosh(x)$?

Suppose that $x\in\mathbb{R}^+$ and $n\in \mathbb{N}$. If $\cosh(nx)$ and $\cosh((n+1)x)$ are rational, can we show that $\cosh(x)$ is rational too? I guess the following equalities should be useful: ...
0
votes
0answers
46 views

If $\gcd(a,b) = \gcd(c,d) = 1$ and $ab = cd$, then $a=c$ and $b=d$. [closed]

Is this conjecture true? If yes, can somebody help me prove it? If not, can anyone come up with a counter example?
1
vote
1answer
55 views

Can the cardinality of a strictly ordered set exceed the cardinality of the natural numbers?

I'm putting some thought into the CH at the moment and a proof of the answer to this question would be most helpful if anybody would be so kind as to help me out: Can the cardinality of a strictly ...
-1
votes
3answers
26 views

$5x \pmod 7 \equiv 6 \ $ then $\ x \pmod 7 \equiv \ ?$ [closed]

As the question states, if $5x \pmod 7 \equiv 6$ then $x \pmod 7 \equiv $ what? I am not sure how to solve questions of this nature. If you could outline this example so I know how to solve ...
0
votes
0answers
29 views

Z is a subset of Q (the set of all rational numbers)

Let $$n \in Z$$ Then $$n*1=n$$ and so $$n=n/1$$ Note n and 1 are both in Z. so n can be written in the form of $$ z = m/n,\,\,\, where\,\, m,n \in Z\,\,\,and\,\,\, n ≠ 0$$so $$n\in Q$$ Is it enough ...
0
votes
1answer
25 views

Logic Integer Proof with Common Divisors

Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ ...
1
vote
1answer
71 views

Find all the solutions of the congruence $12^x \equiv 17 \bmod 25$

I need to find all the solutions of the congruence $12^x \equiv 17 \bmod 25$. I don't really have an idea how to approach this.. I tried to write it as: $12^x \equiv 17 \mod 25$ ...
1
vote
3answers
52 views

Rational number proposition

**Prop.**Every $$r \in Q$$ can be written as r = m/n, where $$ m,n \in Z$$ such that n>0 and gcd(m,n) = 1 (r is in lowest terms) If I start by saying that let $$r \in Q$$ Then there exist $$a,b \in ...
1
vote
3answers
27 views

Simple-to-play morra game to select m winners from n contestants.

I have m apples and n people (m < n) and we need to play a fair deterministic game to decide who gets the apples. I know how to do this if m is 1 with morra, having each player submit an integer ...
2
votes
1answer
25 views

Classification of moduli where relatively prime numbers squared are 1

I came across an interesting property of certain numbers with respect to modular arithmetic and I was wondering if anybody had any more information about them. Consider an integer $n$ such that if ...
3
votes
3answers
60 views

Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

I need to find all the solutions of the congruence $x^2 \equiv 9 \mod 256$. I tried (apparently naively) to do this: $x^2 \equiv 9 \mod 256$ $\Leftrightarrow$ $x^2 -9 \equiv 0 \mod 256$ ...
4
votes
1answer
95 views

How many divisors does $111…1$ have?

Let $A=\underbrace{11..1}_{2010}$. How many divisors does $111...1$ have? Original problem: Prove that $τ(A)>50$ (or $τ(A)<50$) My work so far: If $\tau(A) -$ the number of divisors ...
2
votes
1answer
74 views

A seemingly-trivial divisibility conjecture

While working on another problem, I stumbled on the following divisibility claim. Conjecture: No integers $a,b,c,d$ satisfy all of the following conditions: $a^2+b^2-c^2-d^2 = 2(ad-bc)-1$; ...
1
vote
1answer
18 views

If $\sigma(N)$ is odd, $N = 2y^2$, and $y$ is not a power of two, does it follow that $\gcd(2,y) = 1$?

Let $\sigma(N)$ denote the sum of the divisors of the number $N$. It is well-known that $$\sigma(N) \equiv 1 \pmod 2 \iff \left\{\{N = x^2\} \lor \{N = 2y^2\}\right\}.$$ Here is my question: If ...
2
votes
1answer
29 views

How to find a square root mod $pq$ given that $p \equiv q \equiv 3 \pmod 4$

Let $n = pq$ where $p$ and $q$ are prime. We do not know $p$ and $q$. All we know is that $p \equiv q \equiv 3 \pmod 4$. From this we need to find a number $y$, in terms of $n$ and $x$, such that $y^2 ...
0
votes
1answer
21 views

Understanding a proof from Rotman's “Advanced Modern Algebra”(Chinese Remainder Theorem)

Please, read this post. I don't need to find any proof of the theorem, a I need to understand a specific step in a stecific proof. This is the proof from J.Rotman's book "Advanced Modern Algebra" 3rd ...
5
votes
4answers
59 views

Total number of integers relatively prime to $p^2$

I am reading my number theory textbook and it states without proof that the total number of elements relatively prime to $p^2$ for some prime $p$ is $p(p-1)$. Why is this so? I know that the number of ...
5
votes
2answers
47 views

Rational Question for $a + b$ and Irrationality of $a^2 + b^2$

I have looked into the question and need help. Find some $a,b$ ${\in}$ $\mathbb{R}$ such that $a + b$ ${\in}$ $\mathbb{Q}$, $a^2 + b^2 \not\in \mathbb{Q}$, and $\frac{a}{2} < b < a$. Or prove ...
1
vote
1answer
48 views

I get a wrong answer for the gcd of two polynomials

Hello first post here, I am trying to get the gcd of the two polynomials using the euclidean algorithm, but as result I get a fraction with huge numbers, instead of 1, which I get as result after ...
0
votes
1answer
25 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
2
votes
3answers
53 views

For $a,b>2$, $a,b\in \Bbb{N}$ , prove that $2^a+1$ is never divisible by $2^b-1$ [duplicate]

I have to prove that for $a,b>2$, $a,b\in \Bbb{N}$ that $2^a+1$ is never divisible by $2^b-1$. The method I used is by taking cases, first of them being $b>a$. Now since $b>a$ implies ...
0
votes
2answers
51 views

How do you split a fraction into a sum of fractions?

To add: $$\frac25+\frac37=\frac{14+15}{35}=\frac{29}{35}$$ But if asked to return $\frac{29}{35}$ to a sum of fractions how would one go about this? My attempt: ...
3
votes
2answers
50 views

The condition about some positive real numbers can be written as the sum the nearby two

Given $n$ positive real numbers $x_1,...,x_n$. What is the condition that they can be written as $$x_1=y_1+y_2$$ $$x_2=y_2+y_3$$ $$\ldots$$ $$x_n=y_n+y_1$$ where $y_1,\ldots,y_n$ are also some ...
1
vote
1answer
27 views

all pairs of a and b in an equation containing gcd

Find all pairs of positive integers $a,b$ such that $$ab=160+ 90\cdot \gcd(a,b)$$ how do we approach this type of problem in number theory or what is the best way to solve this ?Here gcd is greatest ...
-11
votes
3answers
178 views

Please attempt to fault my proof of the continuum hypothesis [closed]

I have put this proof of the continuum hypotheses to both a Dr. of Maths and a Professor of Logic, and neither has demonstrated a flaw - although I doubt the professor (who shall remain nameless) ...
0
votes
0answers
23 views

Prove one prime occurring to at least the t-th power

Prove that for all pairs of positive integers s and t, there are infinitely many sequences of s consecutive positive integers, each of which, when factored into prime powers, has at least one prime ...
8
votes
2answers
102 views

Can this puzzle be solved without brute force?

Consider positive integers $a$ and $b$, where $a \ge b$ and the sum $\frac{a+1}{b}+\frac{b+1}{a}$ is also an integer. Find the sum of all $a$ values less than $1000$ that meet this criteria. For ...
1
vote
2answers
43 views

Let $A = (0,1]$. Then $\inf(A) = 0$

I am having a problem with this statement. I am trying to prove that 0 is the greatest lower bound by showing that every lower bound greater than 0 is a contradiction but I can't figure our how. ...
0
votes
5answers
79 views

Proof that if $(n+1)^2 -1$ is even then $n$ is even?

The forward implication, if $n$ is even then $(n+1)^2 -1$ is even, was simple. I can't figure out the other implication: if $(n+1)^2 -1$ is even then $n$ is even. What type of proof do I want to ...
1
vote
5answers
53 views

Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. [duplicate]

Full question: Let $p$ be a prime and let $a$ be an integer such that $1 \leq a < p$. Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. Looking for the ...
2
votes
1answer
45 views

Factorising an integer in $\Bbb{Z}[\sqrt{-2}]$

So I just completed this exercise: My solution involved taking norms, deducing that $N(\alpha)=p$ for some $\alpha\in\Bbb{Z}[\sqrt{-2}]$ which is not a unit. Then supposing $$\alpha=a+b\sqrt{-2}$$ ...
0
votes
0answers
29 views

Question about the solutions to quadratic congruence $x^2\equiv -1(\mbox{mod}\;p)$

As is known to all, when $p\equiv 1(\mbox{mod}\; 4)$, there are 2 solutions to the congruence in the set $\{1,2,3,...p-1\}$: $$x^2\equiv-1(\mbox{mod}\;p)$$ which to be exact are ...
21
votes
2answers
345 views

Is $\frac{1}{11}+\frac{1}{111}+\frac{1}{1111}+\cdots$ an irrational number?

Obviously: $$\frac{1}{10}+\frac{1}{100}+\frac{1}{1000}+\cdots=0.1111\dots=\frac{1}{9}$$ is a rational number. Now, if we make terms with demoninators in the form: $$q_n=\sum_{k=0}^{n} 10^k$$ Then ...
-2
votes
1answer
35 views

Finding the digit in the units place [closed]

Find the digit in the units place of the number $2009!+3^{7886}$. The options available are: a) $7$ b) $3$ c) $1$ d) $9$
1
vote
0answers
38 views

simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
1
vote
1answer
29 views

Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
0
votes
0answers
21 views

Proving that ${p \choose r}$ is an integer for a prime $p$ and $0 < r < p, r \in \mathbb{Z}$ [duplicate]

I need to prove that given integers $p$ and $r$ such that $p$ is prime and $0 < r < p$, ${p \choose r} = \frac{p!}{r!(p-r)!} \in \mathbb{Z}$ As of now, I don't have any ideas on how to proceed. ...
0
votes
1answer
36 views

Understanding proof of $\tau \ (n) =(k_1+1)(k_2+1)\dots(k_r+1)$ and for $\sigma\ (n)$ also.

I recently studied that: $$\tau \ (n) = (k_1+1)(k_2+1) \cdots (k_{r}+1)$$ $$\sigma\ (n) = \frac{p_{1}^{k_1 + 1} -1}{p_1 - 1}{\frac{p_{2}^{k_2 + 1} -1}{p_2 - 1}} \cdots {\frac{p_{r}^{k_r + 1} -1}{p_r - ...