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

learn more… | top users | synonyms (1)

1
vote
1answer
53 views

Number of divisors of a perfect square

Given a number $n$ , let $m$ denote the number of divisors of $n$. Is there a way to express the number of divisors of $n^2$ explicitly through $m$ without using the powers of primes in the ...
1
vote
3answers
76 views

Trying to prove that there are no p and q such that $|\sqrt5 - p/q| < 1/(7q^2)$.

Like the title says, I'm having trouble proving that there are no integers p and q such that $|\sqrt5 - p/q| < 1/(7q^2)$. I was given the hint that $|(q\sqrt5 - p)(q\sqrt5 + p)| \geq 1$, but I ...
0
votes
2answers
97 views

Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively

Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively. Any hints would be appreciated. Thanks!
1
vote
2answers
69 views

How to prove that at least one of $a,b,c,d$ is not divisible by $ad-bc$ if $ad-bc>1$?

we have $ad-bc >1$ is it true that at least one of $a,b,c,d$ is not divisible by $ad-bc$ ? Thanks in advance. Example: $a=2$ , $b = 1$, $c = 2$, $d = 2$, $ad-bc = 2$ so $b$ is not divisible by ...
1
vote
1answer
117 views

Solution set to exponential in congruence

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution? It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed? Any hints would be appreciated. Thanks!
0
votes
1answer
74 views

Is 2(2k-1) is a perfect square for positive integer k?

For positive integer $k$, let $M = 2(2k-1)$, which of the following must be true? (a) $M$ is not a perfect square for any $k$. (b) There are infinitely many $k$ such that $M$ is a perfect square. ...
4
votes
1answer
3k views

How to determine whether a number can be written as a sum of two squares?

I know the following theorems: A number can be represented as a sum of two squares precisely when $N$ is of the form $n^2 \prod p_i$ where each $p_i$ is a prime congruent to 1 mod 4 If the equation ...
1
vote
1answer
173 views

How to use table of indices to solve a congruence?

I have trouble understanding the link between completing a table of indices to the base 3 modulo 17 (for example - which I can do just fine) and being asked to use the table to solve a congruence like ...
3
votes
1answer
67 views

Integer solutions to equations of the form $a^n+b^n+\cdots=c^n$

I shall refer to the number of terms on the left side of the equation as $m$. Suppose that all numbers in the equation are positive integers. I am wondering if anything is known about for which ...
0
votes
1answer
66 views

A form of Chinese remainder theorem

How can we solve equations of the form $c \equiv a \mod b$ for finding the c? Also, sometimes $c$ can be two different numbers, one negative and one positive, when is that possible and how does it ...
1
vote
2answers
111 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
0
votes
3answers
169 views

At least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$

I'm trying to solve a graph theory problem that relies on for any prime $p$ there being at least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$. I believe its true but my number theory is rusty ...
-1
votes
2answers
67 views

Find the natural numbers $n$ in which $n^2$ divides $584$? [duplicate]

I'm trying to find the natural numbers $n$ in which $n^2$ divides $584$ ? i tried all the ways i know but i get stuck.
0
votes
1answer
30 views

Questions on number operations

I took this practice text from University of Houston to prepare for the texes 4-8 math test. They do not show the correct answer if you get a question wrong. Can someone tell me the answer to these ...
1
vote
2answers
48 views

positive integer solutions of $y=\frac{5x}{3x-5}$

Any ideas on how to approach that problem besides brute-force? One solution is (x,y)=(2,10).
1
vote
1answer
64 views

How many different right triangles are possible with the shorter side of odd length?

I was trying to solve this problem but unable to figure it out completely. I thing number of was odd integer $n$ can be the side of right triangle is number of factor of $\frac{n^2}{2}$. Can some one ...
0
votes
0answers
192 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
2
votes
1answer
31 views

On the number of Hall divisors of an integer

A Hall divisor of an integer $n$ is a divisor $d$ of $n$ such that $d$ and $n/d$ are coprime. If $n$ is a positive integer, then $\varphi(n)$ is the number of integers $k$ in the range $1\leq k\leq ...
0
votes
2answers
49 views

If $4xy+3=c^2+3d^2$, is $xy$ necessarily a square?

I have a polynomial which, simplified, ends up in the form $$4xy+3 = c^2+3d^2.$$ Evidently $4xy+3$ is of the form $a^2+3b^2$, in light of the equality. But does $$ c^2 + 3d^2 = 4xy + 3 = xy(2)^2 ...
4
votes
1answer
39 views

powers of $f(x)$ where $f(x)\in\mathbb{Q} [x]\setminus\mathbb{Z} [x]$

Let $n\geq 2$ be an integer. If $f(x)\in\mathbb{Q} [x]\setminus\mathbb{Z} [x]$ can $f(x)^n$ be in $\mathbb{Z}[x]$ ?
0
votes
1answer
49 views

Something wrong with this definition of absolute value function?

In Spivak's book on calculus, the absolute value function has been defined as: $$|x| = \left\{ \begin{array}{ll} x & \mbox{if } x \geq 0 \\ -x & \mbox{if } x \leq 0 \end{array} \right. ...
3
votes
0answers
140 views

Find all positive rational solutions to $x^y = y^x$

Note: This is essentially the same as What are the positive rational solutions of $x^{(x+y)} = (x+y)^y$?, but that did not have any good answers. In my answer to Understanding the graph for $x^y = ...
3
votes
2answers
3k views

Given perimeter of triangle and one side, find other two sides

In triangle ABC, all three sides have integer lengths. If AB = 21, the perimeter is 54, and the area is a positive integer, what are the lengths of BC and AC? I tried using Heron's Formula, but I ...
6
votes
2answers
402 views

Sum of Digits Question

If A is the sum of the digits of $5^{10000}$, B is the sum of the digits of A, and C is the sum of the digits of B, what is C? I know it has something to do with mod 9, but I'm not sure how do use it ...
0
votes
2answers
2k views

Prove the commutativity property of addition of natural numbers by induction

the background I'm allowed to deal with to solve this problem is as follows: Definition of +: \begin{equation} m+0=m\quad \text{for all}\quad m \in \mathbb{N} \\ m+(k+1) = (m+k)+1 \end{equation} in ...
1
vote
3answers
67 views

Can one work with any classes of numbers in a proof of number theory?

Can one work with any classes of numbers, like natural, integer, rational, real and complex, in a proof of number theory, as long as the result tells something about the integers ? Or should the ...
2
votes
2answers
144 views

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = \gcd(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$. We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some ...
0
votes
1answer
61 views

Let $a$ and $b$ be coprime positive integers. Prove that, for any integer $n$, there exist integers $s$ and $t$ such that $sa + tb = n$

I always sort of took this fact for (well..) fact. Can someone help me with the proof? Does this question have something to do with modulus? Since $a$ and $b$ are coprime ($gcd$ = 1), multiplying ...
9
votes
1answer
252 views

Ramanujan's personification of small positive integers

I dimly recall reading somewhere (perhaps in "The Man Who Knew Infinity"?) that Ramanujan associated personalities (perhaps it was mystical personalities, e.g. specific gods and goddesses?) with small ...
0
votes
3answers
670 views

Integers with interesting properties. [closed]

A few weeks ago I found the book "Lure of the Integers" by Joe Roberts, in my schools library, and promptly ordered it from Amazon. It is a wonderful book for those of us who are interested in number ...
0
votes
1answer
66 views

Number theory problem exercise? [closed]

Find all natural numbers $N$ so that $\varphi(N)=24$ where $\varphi$ is Euler's function.
2
votes
1answer
101 views

Help with $\sum_{d\mid n}τ(d)^2=\sum_{d \mid n}τ(d)^3$

I am doing some exercises on number theory on multiplicative number theoretic functions and I have some problems with the multiplication on sums like the sum $\sum_{d\mid n}(τ(d))^2$ where $d$ is a ...
1
vote
2answers
67 views

Simplify sum with factorials

Is there any way to simplify this? $$\sum_{k=1}^{b}\left (\frac{n!}{k!(n-k)!}\right)$$ Edit: Assume that $b \le n$ (Side note: relates to my previous question.)
10
votes
4answers
1k views

How big is a particular n!?

Is there a way to estimate how big $n!$ is for a certain $n$? For example, without using a calculator, what is the magnitude of $7!$ or $12!$ or $100!$?
0
votes
2answers
44 views

A diophantine question about squares

I have been trying to solve the following problem: Classify triples of integers $(m,n,k)$ satisfying the following equation $2mn+m+n=k^{2}$. It is very easy to obtain some solutions. However, I am ...
1
vote
1answer
138 views

What is zero times zero

What is zero zeros? What are no nothings? From a mathematical point of view it would be my thing, but none of us are educated that much in math, so I am curious to hear an expert opinion.
2
votes
2answers
130 views

Proving that repeating decimals can be rewritten as fractions without using infinite series

I'm being asked to prove that all repeating decimals can be written as fractions. The catch is that I'm not allowed to use infinite series, so that excludes most if not all methods I've seen so far. ...
0
votes
2answers
53 views

If $p~ \mid~ m^p + n^p$, prove $p~ \mid~ \frac{m^p + n^p}{m+n}$. [duplicate]

If $p \mid m^p + n^p$, and $p$ is a prime greater than $2$, prove $$p \mid \frac{m^p + n^p}{m+n}.$$ No clue how to start. Clearly $p \mid m + n$, but then what. I feel very less information is given. ...
2
votes
2answers
46 views

How do we know $ n $ is a multiple of $ 2 $ from the equation $ 2 =\frac{ n^2} { d^2} $?

My attempt at answering starts by observing that if a number $ n $ is a multiple of $ 2 $, then it can be written in the form $ n = i \cdot 2 $ where $ i $ is some integer. Now I assume that there is ...
3
votes
2answers
397 views

The sum of all possible values of N

The product $N$ of three positive integers is 6 times their sum, and one of the integers is the sum of the other two. Find the sum of all possible value of $N$. Based the given, I think the sum would ...
0
votes
2answers
44 views

Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7. I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using ...
3
votes
1answer
113 views

Number of 3x3 matrices with determinant $1$ and coefficients in $\mathbb{Z}_5$

Let $M=(m_{ij}), m_{ij} \in \mathbb{Z}_5$. $det(M) \in \{0,1,2,3,4\}$. There are equal number of matrices with determinants $1,2,3$ and $4$, because determinant is multiplied by $2$ when one of rows ...
1
vote
2answers
187 views

Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm?

Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate ...
0
votes
2answers
64 views

Last Two digits of

How to calculate the last two digits of ${14}^{{14}^{14}}$?With the help of any method.I have tried and have got the last digit to be 6 . But not sure.
0
votes
1answer
59 views

Error in this Chinese Remainder Theorem problem with three congruence equations?

Origin - p5 - Example 5 I'm querying a possible error, thence I show the pdf as is. Is the 3 underlined in red supposed to be 2? scilicet, the last line should be $n = 2 \times 5 \times 7 $? Notation ...
0
votes
1answer
27 views

When will three cycles line up?

Three seniors x,y, and z live in a complex and love eating pizza. X eats pizza every 5 days, y every 7 days, and z every 11 days. X & Z had pizza together yesterday and Y had pizza today. When ...
-1
votes
2answers
54 views

Verify that 4(29!)+5! is divisible by 31. [duplicate]

Verify that 4(29!)+5! is divisible by 31. How do I work this out? Step by step explanation please!
0
votes
3answers
26 views

Prove if $\gcd(a,m)=1$ then $\gcd(a \mod m,m)=1$.

Prove if $\gcd(a,m)=1$ then $\gcd(a \mod m,m)=1$. Is there some simple elegant way of proving the above statement? I prove it by noting $div(a,m)=div(a\mod m,m)$, but it is a bit lengthy.
4
votes
0answers
85 views

Application of Dirichlet Theorem in AP to elementary number theory problems.

I have learnt this theorem in my class, however, "elementary" examples are very limited. (focusing more on analytic machinery) Are there any interesting applications to elementary number theory that ...
2
votes
0answers
77 views

How to prove sum of two numbers of the two following forms can be equals to sum of two numbers not of the forms?

The two forms are: $\ 3x^2 + (6y-3)x - y\ $ $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+}$ For example: $\ \ \ 5 = \ 3*1^2 + (6*1-3)*1 - 1\ $ ,when $\ x = y = 1\ $,of the two forms $\ ...