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

learn more… | top users | synonyms

0
votes
2answers
307 views

Factoring for extremely large numbers that are a power of 2.

This is a variation of this question. I want to find the number of factors for a given large integer that I already know to be a power of 2. Given that the number is a power of 2, does that help by ...
10
votes
2answers
481 views

If $a^n-b^n$ is integer for all positive integral value of $n$, then $a$, $b$ must also be integers.

If $a^n-b^n$ is integer for all positive integral value of n with a≠b, then a,b must also be integers. Source: Number Theory for Mathematical Contests, Problem 201, Page 34. Let $a=A+c$ and ...
3
votes
2answers
137 views

Trivial solution when solving in integers

Suppose we want to solve $4(x+y)^{2}-3xy-6(x+y)=0$ where $x$ and $y$ are both integers. Why we only get the trivial solution?
1
vote
5answers
266 views

What is the units digit of $13^4\cdot17^2\cdot29^3$?

What is the units digit of $13^4\cdot17^2\cdot29^3$? I saw this on a GMAT practice test and was wondering how to approach it without using a calculator. Thanks.
2
votes
2answers
174 views

Elementary Number Theory (GCD)

Statement to be proved: Assuming that $(a, b) = 2$, prove that $(a + b, a − b) = 1$ or $2$. I was thinking that $(a,b)=\gcd(a,b)$ and tried to prove the statement above, only to realise that it is ...
-1
votes
1answer
143 views

What are the confusions in the Theory of Numbers?

What are the confusions & resolution(if any) , those have occurred in the history of the Theory of Numbers? I have come across : Is 1 a prime number:counter proof? Is 0 a natural number: no ...
1
vote
1answer
556 views

Modulus Distributing Over Multiplication?

Given positive integers a,b,c and k: Define a function $M: \mathbb{Z^2} \rightarrow \mathbb{Z}$ as $$M(x,y) = (x \bmod y)$$ i.e. the remainder of integer division The following is always true: ...
0
votes
1answer
39 views

Sum of mutliples b/w $2$ and $10$ . What is wrong with this method

I am trying to find the sum of multiples b/w $2$ and $10$ end points non-inclusive using the following mechanism and I don't know why I am getting the wrong answer. (I selected this small range ...
2
votes
4answers
114 views

Are the two statements concening number theory correct?

Statement 1: any integer no less than four can be factorized as a linear combination of two and three. Statement 2: any integer no less than six can be factorized as a linear combination of three, ...
9
votes
4answers
3k views

Is there a way to determine how many digits a power of 2 will contain?

Is there a direct way to determine how many digits a power of 2 will contain without actually performing the multiplication? An estimation would help as well if there is no absolute solution. EDIT: ...
1
vote
1answer
106 views

prove existence of integers $a,q$ which satisfy the following inequality

Let $x \in \mathbb{R}$ and integer $Q \geq 1$. Prove: there exist integers $a$ and $1 \leq q \leq Q$ such that $|x - \frac aq | < \frac 1{qQ} $ any help would be appreciated!
0
votes
1answer
141 views

Which value is greater ? Sum of same four numbers or 36

I came across the following question The average of four numbers is 36. Which is greater Sum of same four numbers or $140$ Now the answer states (a- The sum of same four numbers). How ...
1
vote
5answers
857 views

Minimum value of $x+y$ when $xy=36$

How would I calculate minimum value of $x+y$ when $xy=36$ and x and y are unequal positive integer numbers. I don't even know the answer. Any help would be appreciated. Edit: Sorry It was the ...
1
vote
4answers
1k views

What digit appears in unit place when $2^{320}$ is multiplied out

Is there a way to answer the following preferably without a calculator What digit appears in unit place when $2^{320}$ is multiplied out ? a)$0$ b)$2$ c)$4$ d)$6$ e)$8$ ---- Ans(d)
4
votes
3answers
277 views

Properties and identities of $\text{ord}_{p}(n)$

$\mathrm{ord}_{p}(a+b)\ge\mathrm{min}(\mathrm{ord}_{p}a,\mathrm{ord}_{p}b)$ with equality holding if $\mathrm{ord}_{p}a\ne \mathrm{ord}_{p}b$. is a the statement that prompted this question. It was ...
1
vote
4answers
948 views

What is smallest possible integer k such that $1575 \times k$ is perfect square?

I wanted to know how to solve this question: What is smallest possible integer $k$ such that $1575 \times k$ is a perfect square? a) 7, b) 9, c) 15, d) 25, e) 63. The answer is 7. ...
1
vote
4answers
1k views

How many int. values of n will the expression be greater than 1

How would I solve this problem: How many integer values of n will the expression $4n+7$ be an integer greater than 1 and less than 200 a)48 b)49 c)50 d)51 e)52 ? Ans 50 I am trying to ...
4
votes
1answer
75 views

Number of combinations of sets over a function.

Does anyone know if the following question has been solved in general or has any insight in the question. Let us take for example the sets {0,1} and {1,2} and function multiplication (*) over the ...
5
votes
2answers
321 views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is ...
2
votes
2answers
199 views

How to find all solutions to equations like $3x+2y = 380$ using matrices/linear algebra?

I'm coming up blank on Wikipedia and other sources, though this seems elementary. I'd like to know what techniques or processes are used to find all (integer) solutions to an equation such as $3x+2y = ...
5
votes
5answers
2k views

Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$

I'm working on a homework problem that is as follows: Suppose that $n$ is a positive even integer with $n/2$ odd. Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$. ...
1
vote
1answer
73 views

If $(m_1,m_2)=D$, $(a,m_1)=d_1$, $(b,m_2)=d_2$, then $(am_2+bm_1, m_1m_2)=?$

We know, If $(m_1,m_2)=(a,m_1)=(b,m_2)=1, \iff (am_2+bm_1, m_1m_2)=1$ I tried to generalize now. Let $(a,m_1)=d_1, (b,m_2)=d_2$ where $d_1,d_2$ need not to be 1. $(am_2+bm_1, m_1m_2)$ ...
3
votes
0answers
136 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
2
votes
3answers
113 views

Proving that if $p$, $q$ are rationals and $p < q$, then there is a rational $v$ such that $p < v < q$

The question itself looks pretty simple, but I'm a complete beginner and have no idea where to start. Any help would be greatly appreciated Proving that if $p$, $q$ are rationals and $p < q$, then ...
2
votes
3answers
2k views

Proving that for each prime number $p$, the number $\sqrt{p}$ is irrational [duplicate]

Possible Duplicate: $\sqrt a$ is either an integer or an irrational number. I'm a total beginner and any help with this proof would be much appreciated. Not even sure where to begin. ...
3
votes
1answer
151 views

What is the highest power of $n$ in $(n^r-1)!$

What is the highest power of n in $(n^r-1)!$ where $n$, $r$ are positive integers? The answer supplied is $\frac{n^r-nr+r-1}{n-1}$ The highest power of $n$ in $n^r! = r +$ the highest power of $n$ ...
2
votes
2answers
127 views

How many elements $a \in \Bbb{Z}_N$ such that $ax \equiv y \mod N$

Consider the ring $\Bbb{Z}_N$ of arithmetic modulo $N$: $\{0,1,2, \ldots ,N-1\}.$ Given $x,y \in \Bbb{Z}_N,$ how many of the elements of $\Bbb{Z}_N$ when multiplied with $x \pmod{N}$ result in $y$? ...
3
votes
9answers
205 views

If both $a$ and $b$ $\not \equiv 0 \pmod{p}$ then $ab \not\equiv 0 \pmod{p}$

Any help with this proof would be great. Not even sure where to begin. I'm pretty much a total newbie. If $a$ is not congruent to $0 \pmod{p}$ and $b$ is not congruent to $0 \pmod{p},$ where $p$ ...
0
votes
3answers
213 views

If $p$ is a factor of $m^2$ then $p$ is a factor of $m$

I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated. If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ ...
2
votes
3answers
292 views

Is this statement stronger than the Collatz conjecture?

$n$,$k$, $m$, $u$ $\in$ $\Bbb N$; Let's see the following sequence: $x_0=n$; $x_m=3x_{m-1}+1$. I am afraid I am a complete noob, but I cannot (dis)prove that the following implies the ...
1
vote
0answers
103 views

Does the shifting square root method work for non-integer bases?

Under "methods of computing square roots", Wikipedia states that the digit-by-digit calculation method, of which the shifting $n^{th}$ root algorithm is a generalization, works for all bases, but the ...
1
vote
1answer
284 views

Convergence of a series of reciprocal prime numbers

If $p$ is a prime number, and $q$ is its twin prime, the sum of the reciprocal twin numbers is convergent and the value of the sum of the series is the Brun constant. Now, if we consider the prime ...
1
vote
2answers
72 views

A Trivial Question - Increasing by doubling a number when its negative

The question is : if $x=y-\frac{50}{y}$ , where x and y are both > $0$ . If the value of y is doubled in the equation above the value of x will a)Decrease b)remain same c)increase four fold ...
1
vote
0answers
51 views

Minimal fractional representation in $\Bbb Z/p\Bbb Z$

I arrived to needing an algorithm for the following subproblem while solving a more complex problem. It seems it should be a very standard algorithm, but my number theory isn't too fresh so I haven't ...
0
votes
1answer
85 views

Largest positive integer $k$ such that $\mu(n+r)=0$ for all $1\leq r\leq k$

Find the largest positive integer $k$, such that $\mu(n+r)=0$ for all $1\leq r\leq k$ where $r,n$ are positive integers. As far as I could make out, we need to find out the maximum range(if nay) ...
7
votes
3answers
263 views

Solving simple congruences by hand

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding ...
17
votes
2answers
606 views

Multiplication tables with all entries distinct

Let positive integers $\alpha$ and $\beta$ be given. It is easy to find sets $A$ and $B$ of positive integers such that: $|A|=\alpha$ and $|B|=\beta$ The set $P = \{ab : a\in A, b\in B\}$ contains ...
1
vote
1answer
114 views

What values can $n$ assume, when $z^2+n= x^2+y^2$?

$x^2+y^2 =n +z^2$ where $x,y,z$ are different natural numbers. What values can $n$ assume? What if x,y,z>0 considering the confusion of 0 as natural number?
6
votes
8answers
390 views

Divisibility of composite numbers

I am having difficulty in solving following types of problem: Sometimes we are given a number in terms of $n$ and we have to check whether it is divisible by a particular composite number. For ...
0
votes
3answers
142 views

Given that $5n$ is a square and $75np$ is a cube, why is the smallest possible value of $n+p$ equal to $14$?

I can't solve this problem: Suppose $n$ and $p$ are integers greater than $1$, $5n$ is the square of a number, and $75np$ is the cube of a number. What is the smallest value for $n+p$? ...
2
votes
3answers
95 views

The square of every integer is of the form either $3k+1$ or $3k$

How can I prove that square of every integer is of the form either $3k+1$ or $3k$, but not $3k+2$? My approach I considered first, the integer $n$ to be even and then $n= 2m$; and if $n$ is odd ...
0
votes
2answers
106 views

Average of numbers in a specific range

The question is : What is the arithmetic mean of all multiples of 10 from 10 to 190 inclusive. Now I know how many nos there are by using $\frac{190-10}{10}+1 = 19$ but how do I get ...
2
votes
1answer
430 views

A power-exponential congruence equation

Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$ My thought: ...
3
votes
1answer
351 views

How to efficiently compute the order of a prime number mod $l$ [duplicate]

Possible Duplicate: Quick algorithm for computing orders mod n? Let $l$ be an odd prime number. Let $p$ be a prime number such that $p \neq l$. I'd like to compute efficiently the order of ...
4
votes
1answer
124 views

If $A,B$ are factors of $2^6 3^4 5^2,$ how many values of $|A-B|$ are possible?

Let $x=2^6 3^4 5^2$, then how many distinct values of $|A-B|$ are possible where $A, B$ are the factors of $x$? How to approach this problem?
3
votes
1answer
158 views

Integers of the form $a^2+b^2+c^3+d^3$

It's easy$^*$ to prove that if $n=3^{6m}(3k \pm 1)$ where $(m,k) \in \mathbb{N} \times \mathbb{Z}$, then $n=a^2+b^2+c^3+d^3$ with $(a,b,c,d) \in \mathbb{Z}^4$. But how to prove that this is true if ...
1
vote
2answers
118 views

Unique number for multiplication

I am looking for a number that when multiplied by any number and divided by 10000 never leaves the 3 digit number as 291 , I mean I am looking for a number that leaves a remainder as 1231 , 1001 ...
0
votes
1answer
661 views

Cyclotomic polynomial over a finite prime field [duplicate]

Possible Duplicate: Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})\[X\]$ Let $p$ be a prime number. Let $l$ be an odd prime number such that $l \neq p$. Let $X^l - 1 \in ...
2
votes
3answers
603 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
6
votes
1answer
136 views

Is there a name for the “most square” factorization of an integer?

For the definition that follows, I'm curious to know if there's a known name (to enable a literature search relating to algorithms). Definition. Given an integer $n$, the maximally square ...